4883

삼각그래프

알고리즘 문제를 풀 때 가장 기본적인 태도는

1. 먼저 문제를 잘 읽는다

2. 문제를 의심한다

여기선 문제를 잘 읽기는 했는데 문제를 의심하는 단계가 부족했다.

입력으로 비용의 제곱은 1000000보다 작다고 했는데 그렇다면 비용은 음수가 들어올 수도 있다는 이야기...

하지만 나는 그걸 몰랐고 쓸데 없이 틀렸다.

그런데 이런건 좀 친절히 설명해줘야 하는거 아닌가 ㅡㅡ

#include<iostream> #include<cstdio> using namespace std; int main() { int cost[3], clk=0; long long cur[3], bef[3]; int n; while(true){ scanf("%d", &n); if(n==0) break; for(int i = 0; i < n; i++){ for(int j = 0; j < 3; j++) scanf("%d", &cost[j]); if(i == 0){ cur[0] = cost[1]; cur[1] = cost[1]; cur[2] = cost[1]; if(cost[2] < 0){ cur[2] = cur[1] + cost[2]; //가운데 점을 오른쪽으로 이동시켜준다. } } else if(i == 1){ cur[0] += cost[0]; cur[1] = cost[1] + min(bef[1], bef[2]); cur[2] = cost[2] + min(bef[1], bef[2]); cur[1] = min(cur[1], cur[0]+cost[1]); cur[2] = min(cur[2], cur[1]+cost[2]); } else{ cur[0] = cost[0] + min(bef[0], bef[1]); cur[1] = cost[1] + min(bef[0], min(bef[1], bef[2])); cur[2] = cost[2] + min(bef[1], bef[2]); cur[1] = min(cur[1], cur[0]+cost[1]); cur[2] = min(cur[2], cur[1]+cost[2]); } bef[0] = cur[0]; bef[1] = cur[1]; bef[2] = cur[2]; } clk++; printf("%d. %lld\n", clk, cur[1]); } return 0; }