글 읽기 - dp 문제 질문입니다.

dwhylee 7년 전 0

수정합니다.

2   1 2  > 2
3   1 3  > 3
4   2 2 > 4
5   2 3 > 6
6   3 3    2 2 2   1 2 3 > 9
7   3 2 2 2 2 3   1 3 3 > 12
8   4 2 2 3 3 2   2 3 3 > 18
9    4 3 2 3 3 3 2 4 3 > 27
10   5(2 3) 5(2 3) 4(2 2) 3 3 3 3 2 2   2 3 3 2 1 3 3 3   > 36
11   5(2 3) 3 3   4(2 2) 3 2 2   3 3 3 2                    > 54

이렇게 구한것을 봤을 떄 2와 3을 가지고 어떻게 하면 될 것같은데 이것을 점화식으로 만들어낼 떄
사고 과정을 어떻게 해야하는지도 궁금하네요..
--------------------------------- 수정 ------------------------------------------------

3+4 // 3*4 보고 약간 힌트를 얻어서 코드를 수정해봤는데,
그래도 답이 틀리게 나오네요.
여전히 10007 부분이 잘 이해가 안되네요

#include <iostream>
#include <queue>
using namespace std;
long long dp[1000001];

int main(){
	long long cnt;
	cin >> cnt;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	for (int i = 4; i <= cnt;  i++){ 
        // 둘다 틀렸습니다.
        dp[i] =  max( dp[i - 2] * 2 , dp[i - 3] * 3 ) % (10007);
        dp[i] =  max( ( dp[i - 2] * 2 )% (10007) , (dp[i - 3] * 3) % (10007)) ;
	}
	cout << dp[cnt];
}
/*
	for (int i = 4; i <= cnt;  i++){ 
		if (dp[i - 2] * 2 < 0 || dp[i-3]*3 < 0)
			dp[i] = max((dp[i - 2] % 10007) * 2, (dp[i - 3] % 10007 * 3));
		else
			dp[i] =  max( dp[i - 2] * 2 , dp[i - 3] * 3 ) ;
	}
	cout << dp[cnt] % 10007;
    이렇게도 해봤는데 답은 아니었습니다 ㅜ..
*/

/*
long long dp[1000001];        제일 초기 code
long long returnValue;
long long f(long long num){
	if (dp[num] == 0){
		long long dv = (num / 2);
		for (long long i = dv; i > 0; i--){
			returnValue = max(returnValue, ( dp[num-i] * dp[i] ) );
		}
	}
	return returnValue;
}
int main(){
	long long cnt;
	cin >> cnt;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	for (int i = 4; i <= cnt;  i++){ // 25 26 50 51
		dp[i] = (f(i) % 10007);
		returnValue = 0;
	}
    cout << dp[cnt]
}
*/

baactree 7년 전 0

맨처음 디피식은 맞아요

하지만 모듈라 연산을 하면 최댓값을 찾는 과정이 이상해지죠

10006 < 10008

이지만 모듈라하면

10006 > 1

더 작은값을 최댓값이라고 판단하고 저장하겠죠

dwhylee 7년 전 0

@baactree 그 생각은 했었는데, 그래서 i-3부터 모듈라 연산으로도 생각해봤지만 정확한 답이 안나오는것 같아 아직 해결 못했습니다.

혹시 힌트좀 주실 수 있나요?

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

문제

문제

출처

ICPC

dp 문제 질문입니다.

dwhylee 7년 전 0

baactree 7년 전 0

dwhylee 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말