글 읽기 - 암호코드 DP 점화식, 틀린 부분있는것 같나요! 봐주세요

skfnxh0124 6년 전 0

d[i][1] : i번째 자리가 하나로 묶이는 (1,2,3,4,5,6,7,8,9) 경우의 암호코드의 갯수

d[i][2] : i번째 자리가 앞의 것과 하나가 되는 암호코드의 갯수(10,11,...26)

경우마다 생각을 해줬습니다.

for문 중간의 return 0;은 혹여나 30,40 과 같은 암호로 만들수 없는 경우에는 0을 출력하게 코드를 짰습니다. (사실 이걸 넣고 안 넣고는 차이가 없었습니다.)

점화식이 혹시 틀린부분이 있나요! 제가 미처 생각하지 못한 부분이 어딜까요!

#include<iostream>
#include<cstdio>

using namespace std;
//
int map[5001];
long long d[5001][3];

int zari = 1;
//


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	while (true)
	{
		char temp;
		temp = cin.get();
		if (temp == '\n' || temp == EOF)
		{
			zari--;
			break;
		}
		map[zari] = temp - '0';
		zari++;
	}
	if (map[1] == 0)
	{
		cout << 0;
		return 0;
	}
	
		d[1][1] = 1;
	for (int i = 2; i <= zari; i++)
	{
		if (map[i - 1] >= 7 && map[i - 1] <= 9)
		{
			if(map[i]!=0)
				d[i][1] = d[i - 1][1] % 1000000;
			else
			{
				cout << 0;
				return 0;
			}
		}
		else if (map[i - 1] >= 3 && map[i - 1] <= 6)
		{
			if (map[i] != 0)
				d[i][1] = (d[i - 1][1] + d[i - 1][2]) % 1000000;
			else
			{
				cout << 0;
				return 0;
			}
		}
		else if (map[i - 1] >= 1 && map[i - 1] <= 2)
		{
			if (map[i] == 0)
				d[i][2] = d[i - 1][1]% 1000000;
			else
			{
				d[i][1] = (d[i - 1][2] + d[i - 1][1])% 1000000;
				d[i][2] = d[i - 1][1]% 1000000;
			}
		}
		else if (map[i - 1] == 0)
		{
			if(map[i]!=0)
				d[i][1] = d[i - 1][2] % 1000000;
			else
			{
				cout << 0;
				return 0;
			}
		}
	}




	cout << (d[zari][1]+d[zari][2])% 1000000;
	
	
}

atomzeno 6년 전 1

반례: 1111737-->결과:5(실제결과: 8맞나?)

skfnxh0124 6년 전 1

감사합니다! 앞에 숫자가 7~9여도 2개를 묶어서 1,7~9도 가능하니 저쪽 선언이 잘 못됐네요!

그래도 아직 오답이지만 덕분에 틀린부분찾을수잇었습니다!!

skfnxh0124 6년 전 0

자답입니다!!

58~ if문에서 27,28,29도 하나의 암호로 생각해버렸네요 ..

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

문제

문제

출처

ICPC

암호코드 DP 점화식, 틀린 부분있는것 같나요! 봐주세요

skfnxh0124 6년 전 0

atomzeno 6년 전 1

skfnxh0124 6년 전 1

skfnxh0124 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말