글 읽기 - 이해가 안갑니다. 두 코드에 무슨 차이가 있나요?

ruz 4년 전 0

다른 변경점없이 for문만 바꾼 두 코드의 결과가 상이합니다...

언뜻 보기엔 차이가 없어보이는데 왜 다른 결과가 나오는걸까요?

//Wrong Answer
for(int i =-3; i<=3; ++i) {
    if (!i) continue;
    ref = min(ref, 1 + dp(a, r(f + i), s, t));
    ref = min(ref, 1 + dp(a, r(f + i), r(s + i), t));
    ref = min(ref, 1 + dp(a, r(f + i), r(s + i), r(t + i)));
}


//Accept
for(int i =-3; i<=3; ++i) {
    if (!i) continue;
    ref = min(ref, 1 + dp(a, r(f + i), s, t));
}
for(int i =-3; i<=3; ++i) {
    if (!i) continue;
    ref = min(ref, 1 + dp(a, r(f + i), r(s + i), t));
}
for(int i =-3; i<=3; ++i) {
    if (!i) continue;
    ref = min(ref, 1 + dp(a, r(f + i), r(s + i), r(t + i)));
}






//코드 전문
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;

int n, d[101][11][11][11];
string src, dst;

int r(int a) { return (a + 10) % 10; }
int dp(int a, int f, int s, int t) {
	if (a == n) return 0;
	if (f == (dst[a] - '0')) return dp(a + 1, s, t, src[a + 3] - '0');
    
	int & ref = d[a][f][s][t];
	if (ref != -1) return ref;
    
	ref = 1e9;
	for(int i =-3; i<=3; ++i) {
		if (!i) continue;
		ref = min(ref, 1 + dp(a, r(f + i), s, t));
	}
	for(int i =-3; i<=3; ++i) {
		if (!i) continue;
		ref = min(ref, 1 + dp(a, r(f + i), r(s + i), t));
	}
	for(int i =-3; i<=3; ++i) {
		if (!i) continue;
		ref = min(ref, 1 + dp(a, r(f + i), r(s + i), r(t + i)));
	}
	return ref;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(d, -1, sizeof d);
	cin >> n >> src >> dst;
	src += "000";
	cout << dp(0, src[0] - '0', src[1] - '0', src[2] - '0') << endl;
}

sait2000 4년 전 1

글쎄요 왜일까요 반례 드립니다

sait2000 4년 전 0

그 이유는 바로 둘 다 틀렸는데 데이터가 약해서 그렀습니다 https://www.acmicpc.net/board/view/44245

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

문제

문제

출처

ICPC

이해가 안갑니다. 두 코드에 무슨 차이가 있나요?

ruz 4년 전 0

sait2000 4년 전 1

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말