글 읽기 - 1463 1로만들기 왜때문에 안되는건지 궁금합니다!

gomamon 7년 전 0

dp를 이용해 풀었습니다!

예외인 경우를 못찾겠습니다.엉어유ㅠ

왜 틀리는지 모르겠습니다! 알려주세요!!

2가지로 풀어봤는데 둘다안되더라구요!

/////////////////////////첫번째
#include<stdio.h>
#include<algorithm>
using namespace std;

int dp[1222222];

int main(){
	int n;
	scanf("%d",&n);
	dp[1200000] = 1999999;
	dp[0] = 0;
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	for(int i=4; i<=n ; i++){
		int one=0 ,two=1200000 ,three=1200000;
		one = i-1;
		if(i%2==0) two = i/2;
		else if(i%3==0) three = i/3;
//		printf("dp[%d] : one=%d two=%d three%d\n",i,dp[one],dp[two],dp[three]);
		dp[i] = min(dp[one]+1, min(dp[two]+1, dp[three]+1));
	}
	printf("%d\n",dp[n]);

}

//////////////////2번째///////////////
#include<stdio.h>
#include<algorithm>
using namespace std;

int dp[1222222][4];

int main(){
	int n;
	int Long=1999999;
	scanf("%d",&n);
//	dp[1200000] = Long;
	dp[0][1] = 0;
	dp[0][2] = 0;
	dp[0][3] = 0;
	dp[1][1] = 0;
	dp[1][2] = 0;
	dp[1][3] = 0;
	dp[2][1] = 1;
	dp[2][2] = 1;
	dp[2][3] = Long;
	dp[3][1] = 2;
	dp[3][2] = Long;
	dp[3][3] = 1;
	for(int i=4; i<=n ; i++){
		dp[i][1]=min(dp[i-1][1]+1,min(dp[i-1][2]+1,dp[i-2][3]+1));

		if(i%2==0){
			dp[i][2]=min(dp[i/2][1]+1,min(dp[i/2][2]+1,dp[i/2][3]+1));
		}
		else dp[i][2]=Long;

		if(i%3==0){
			dp[i][3]=min(dp[i/3][1]+1,min(dp[i/3][2]+1,dp[i/3][3]+1));
		}
		else dp[i][3] =Long;
	//	printf("%d - dp1 : %d ,dp2 : %d ,dp3 : %d\n",i,dp[i][1],dp[i][2],dp[i][3]);
	}
	printf("%d\n",min(dp[n][1],min(dp[n][2],dp[n][3])));
}

jseo 7년 전 0

첫번째에서 else if를 그냥 if로 바꿔보세요

gomamon 7년 전 0

우주 전 바보였어요ㅠㅠㅠ 감사합니다!

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

문제

문제

출처

ICPC

1463 1로만들기 왜때문에 안되는건지 궁금합니다!

gomamon 7년 전 0

jseo 7년 전 0

gomamon 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말