글 읽기 - c++) 어디가 틀렸는지 모르겠습니다.

jack3319 2년 전 0

dp[i][0] : i번째 자리까지 해독하는데 i번째 수가 1자리로 따로 카운트

dp[i][1] : i번째 자리까지 해독하는데 i-1, i번째 수를 합쳐서 카운트

ex) 25114

dp[4][0] = 4 - (2,5,1,1,4), (2,5,11,4), (25,1,1,4), (25,11,4)

dp[4][1] = 2 - (2,5,1,14), (25,1,14)

이렇게 점화식짜서 dp로 풀고 대회 케이스도 몇 개 해봤는데 맞았습니다.

제출하면 10퍼대에서 틀렸습니다 뜨는데 어디가 문제일까요

#include <iostream>
#include <string>
#define mod 1000000
using namespace std;
int dp[5001][2];

int decoding(string num) {
	if(num[0] == '0')	return 0;
	dp[0][0] = 1, dp[0][1] = 0;
	int len = num.length();
	for(int i = 1; i < len; i++) {
		if(num[i] == '0') {
			if(num[i-1] >= '3')	return 0;
			else {
				dp[i][1] = dp[i-1][0];
				dp[i][0] = 0;
				continue;
			}
		}
		if(num[i-1] >= '3') {
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			dp[i][1] = 0;
		}
		else {
			if(num[i-1] == '2' && num[i] > '6') {
				dp[i][0] = dp[i-1][0] + dp[i-1][1];
				dp[i][1] = 0;
			}
			else {
				dp[i][0] = dp[i-1][0] + dp[i-1][1];
				dp[i][1] = dp[i-1][0];
			}
		}
		dp[i][0] = dp[i][0] % mod;
		dp[i][1] = dp[i][1] % mod;
		//printf("dp[%d] : %d %d\n", i, dp[i][0], dp[i][1]);
	}
	int ans = dp[len-1][0] + dp[len-1][1];
	return ans;
}

int main() {
	string num;
	cin >> num;
	int ans = decoding(num);
	cout << ans << endl;
	return 0;
}

antonwithai 2년 전 1

마지막에 ans 에서 dp의 합을 구할 때도 구한 후에 MOD로 나눠줘야 할 것 같아요~ :)

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

문제

문제

출처

ICPC

c++) 어디가 틀렸는지 모르겠습니다.

jack3319 2년 전 0

antonwithai 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말