글 읽기 - 14퍼에서 틀립니다. 반례를 찾아주세요

ehdqkd31 1년 전 0

안녕하세요.

코드가 14퍼에서 틀립니다.

0에 대한 조건을 전부 처리했다고 생각하는데 어디서 틀리는 지 모르겠습니다.

반례를 찾아주시면 감사하겠습니다.

#include <iostream>
#include <string>

using namespace std;

// 백준 2011 - 암호코드
// 251 => 2511
// 11은 가능한 수
// 2511 가짓수 = 251의 기존 가짓수 + (251 가짓수 중 마지막 1 혼자 있는 가짓수)
// 101, 201처럼 중간에 0 있는 애들 처리해야 함 

// 1301 => 이런 애들 13 01 이렇게 취급 안 하는지 확인 => 05, 06 이런 거 취급 X


int DP[5001];

// 맨 끝에 혼자인 애들 갯수 => 얘네만 기존 DP 값에서 더해줘야 함
int arr[5001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// 입력 없을 때
	if (cin.eof())
	{
		cout << 0;
		return 0;
	}

	string pw;
	cin >> pw;

	// 기저 조건
	DP[0] = 1;
	arr[0] = 1;
	
	// 잘못된 암호
	if (pw[0] == '0')
	{
		cout << 0;
		return 0;
	}

	string tmp;
	for (int i = 1; i < pw.size(); i++)
	{
		tmp = pw.substr(i - 1, 2);
		if (tmp == "00") // 잘못된 암호 (00)
		{
			cout << 0;
			return 0;
		}

		if (pw[i] == '0')
		{
			if (tmp < "30")
			{
				if (i == pw.size() - 1) // 붙일 수 있는 애들만 붙임
				{
					DP[i] = arr[i - 1];
					arr[i] = 0;
				}
				else
				{
					DP[i] = arr[i - 1];
					arr[i] = DP[i - 1];
				}
			}
			else if(i == pw.size()-1) // 마지막이 연결 X (130) => 잘못된 암호
			{
				cout << 0;
				return 0;
			}
			else // 다 띄어서 보냄
			{
				/*
				DP[i] = DP[i - 1];
				arr[i] = DP[i - 1];
				*/
				cout << 0;
				return 0;
			}
			continue;
		}
		else if (pw[i - 1] == '0')
		{
			DP[i] = DP[i - 1];
			arr[i] = DP[i - 1];
			continue;
		}
		
		if (tmp < "27" && tmp >= "01") // 값이 27보다 작으면 => stoi() 느리기 때문에 빠르게 하는 법 찾기
		{
			DP[i] = (DP[i - 1] + arr[i - 1]) % 1000000;
			// 또 혼자인 애들 체크 => 얘도 나머지 연산
			arr[i] = (DP[i] - arr[i - 1]) % 1000000;
		}
		else // tmp >= "27" && tmp <= "99"
		{
			DP[i] = DP[i - 1];
			arr[i] = DP[i - 1]; // 전부 하나씩 남음
		}
		//cout << DP[i] << ' ' << arr[i] <<  endl;
	}

	cout << DP[pw.size() - 1] % 1000000;


	return 0;
}

ehdqkd31 1년 전 0

DP[i]에 나머지 연산을 해서 1000000보다 작아진 후에 arr[i-1]을 빼는 연산을 할 경우 음수가 나오는 경우가 생기기 때문이었습니다(line 97, 99). 이를 수정해서 통과했습니다.

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

문제

문제

출처

ICPC

14퍼에서 틀립니다. 반례를 찾아주세요

ehdqkd31 1년 전 0

ehdqkd31 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말