글 읽기 - 자두나무 질문..

kokoxg2 6년 전 0

dp[T][W][2] 로 T초에 W번 움직였고 1 혹은 2에 위치할 떄 갖는 값으로 설정했습니다.

예제는 다 맞게 돌아가는데 어디서 문제일까요 ..

#include <cstdio>
#include <cstring>

#define max(a,b)(a > b ? a : b)

int dp[1001][30][2], plum[1000], time_limit, moving_limit; 
// DP[T][W][2] : T초에 W번 움직였고 1 혹은 2에 위치해 있을떄 갖는 값
// PLUM[1000] : T초에 떨어지는 자두 위치
// TIME_LIMIT : 자두가 떨어지는 시간
// MOVING_LIMIT : 최대 이동 횟수

int rec(int time, int move_num, int pos); // 재귀 함수 (시간, 이동 횟수, 위치)


int main() {

	scanf("%d %d", &time_limit, &moving_limit);

	for (int i = 0; i < time_limit; ++i)
		scanf("%d", &plum[i]);

	memset(dp, -1, sizeof(dp)); // DP -1로 초기화

	int ans = rec(0, 0, 1); // 0초, 0번 움직임, 1번 위치에서 시작

	memset(dp, -1, sizeof(dp));

	printf("%d\n", max(ans, rec(0, 1, 2))); // 0초, 1번 움직임, 2번 위치에서 시작

	return 0;
}


int rec(int time, int move_num, int pos) {

    /* 기저 사례 */
	if (time == time_limit) return 0; // 자두 떨어지는 시간이 끝난 경우
	if (move_num > moving_limit) return 0; // 이동 횟수가 초과된 경우

	int &ret = dp[time][move_num][pos]; 

	if (ret != -1) return ret; // 이미 방문한 위치인 경우

	ret = (plum[time] == pos ? 1 : 0); // 현재 위치랑 자두의 위치랑 같으면 1, 아니면 0

	// 원래 위치 그대로, 다른 위치로 움직이기
	ret += max(rec(time + 1, move_num, pos), rec(time + 1, move_num + 1, 3 - pos));

	return ret;
}

kokoxg2 6년 전 0

그냥 하던대로 시작 시간을 1초로 바꾸고 다시 문제를 풀이하니 맞네용.. ㅠㅠ

#include <cstdio>
#include <cstring>

#define max(a,b)(a > b ? a : b)

int dp[1011][33][2], plum[1001], time_limit, moving_limit;

int rec(int time, int move_num, int pos);

int main() {

	scanf("%d %d", &time_limit, &moving_limit);

	for (int i = 1; i <= time_limit; ++i)
		scanf("%d", &plum[i]);

	memset(dp, -1, sizeof(dp));

	printf("%d\n", max(rec(1, 0, 1), rec(1, 1, 2)));
	return 0;
}

int rec(int time, int move_num, int pos) {

	if (time > time_limit || move_num > moving_limit)  return 0;

	int &ret = dp[time][move_num][pos];

	if (dp[time][move_num][pos] != -1) return ret;

	ret = (plum[time] == pos ? 1 : 0); // 현재 위치랑 자두의 위치랑 같으면 1, 아니면 0

	// 원래 위치 그대로, 다른 위치로 움직이기
	ret += max(rec(time + 1, move_num, pos), rec(time + 1, move_num + 1, 3 - pos));

	return ret;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자두나무 질문..

kokoxg2 6년 전 0

kokoxg2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말