글 읽기 - 왜 틀렸는지 모르겠습니다..

rdd6584 6년 전 0

dp 이용해서 풀어보려 했는데, 안풀리네요.

반례가 있는걸까요?

아니면 뭔가가 잘못된걸까요?

도와주세요.

#include<stdio.h>

int dp[10001][10];
int vec[10001];
int ob[10001];

int n;

int go(int x, int p){
	if(dp[x][p] != -1) return dp[x][p];
	if(x >= n+1) return 0;

	int c1, c2, temp = (vec[x] + p) % 10;

	if(temp < ob[x]){
		c1 = ob[x] - temp + go(x+1, (p + ob[x] - temp) % 10);
		c2 = 10 + ob[x] - temp + go(x+1, p);
	}
	else if(temp > ob[x]){
		c1 = 10 + ob[x] - temp + go(x+1, (p + 10 + ob[x] - temp) % 10);
		c2 = temp - ob[x] + go(x+1, p);
	}
	else return dp[x][p] = go(x+1, p);
	
	if(c1 < c2)	return dp[x][p] =  c1;
	else return dp[x][p] = c2;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%1d", &vec[i]);
	for(int i = 1; i <= n; i++) scanf("%1d", &ob[i]);
	
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= 9; j++)
			dp[i][j] = -1;

	printf("%d\n", go(1, 0));

}

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다..

rdd6584 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말