[백준 / BOJ] 20925 메이플스토리

문제

출처 : https://www.acmicpc.net/problem/20925

20925번: 메이플스토리

상원이는 메이플스토리를 할 것이다.

 

상원이의 캐릭터가 갈수있는 사냥터의 수 N

상원이가 사냥할 시간 T 가 주어지고,

이후, N개의 줄에 각 던전에 입장하는데 필요한 최소경험치와 시간당 주는 경험치가 주어진다.

 

상원이가 T시간동안 사냥했을때 얻을 수 있는 최대 경험치를 구하는 문제다.

---

풀이

dp로 푼 문제였다.

처음에는 시간을 기준으로 BFS를 돌리면 T*N^2 시간복잡도로 통과 할줄알았으나, 최악의 경우, 완전탐색과 다를바가 없어서 시간초과가 나왔다.

 

결국 dp로 풀게되었는데, dp식은 다음과 같다.

 

dp[사냥터][시간] = 얻을수 있는 경험치의 최댓값 이라하자,

이전 시간 = 이전 사냥터 -> 현재 사냥터로 오는데 걸리는 시간 

dp[사냥터][시간] = Math.max(dp[이전 사냥터][이전시간], dp[사냥터][시간]);

 

주요 소스코드

    private int getMaximumExp(int time){
        if(time > T){
            int ret = 0;
            for(int i = 0; i < N; i++) ret = Math.max(dp[i][T], ret);
            return ret;
        }
        for(int i = 0; i < N; i++){
            if(dp[i][time-1] != -1) dp[i][time] = dp[i][time-1] + dungeon[i].getExp;
            for(int j = 0; j < N; j++){ // 다른경로에서 i로 오는경우
                if(i == j) continue;
                int bTime = time - move[j][i];
                if(bTime <= 0 || dp[j][bTime] < dungeon[i].needExp) continue;
                dp[i][time] = Math.max(dp[i][time], dp[j][bTime]);
            }
        }
        return getMaximumExp(time+1);
    }

문제 이해?를 잘못해서 여러번 틀렸던 문제였다.

 

A사냥터에서 2분 후에 B사냥터로 도착한경우, A[time - 2] = 10일때, B[time] = 2가 되어야한다.

위와 같은 조건에서, dp식을 A[time - 2] = 10일때, B[time+1] = A[time-2]+B[time] 처럼 구현했다가 7퍼에서 계속 틀렸습니다를 맞았다.

얼핏보기엔 차이가 없어보여서 찾는데 굉장히 힘들었던 오류다(찾는 과정도 막 해보다가 우연히 찾게됨..) 

위와 같이 구현할 경우 B[time]을 건너뛰고 B[time+1]을 참조하기때문에, B[time]부분이 초기화되지않고 틀렸습니다를 맞는다.

 

찾은 반례들

 

1.

3 10
0 10
0 20
50 100
0 1 2
1 0 10
10 10 0

출력 : 460

 

2.
3 10
0 1
0 2
1 1000
0 0 8
0 0 8
0 0 0

출력 : 1002

 

3.
3 15
0 10
20 100
0 1
0 5 3
10 10 10
3 1 0

출력 : 920

 

4.
3 15
0 10
20 100
0 1
0 4 3
10 10 10
3 1 0

출력 : 920

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/20925%20%EB%A9%94%EC%9D%B4%ED%94%8C%EC%8A%A4%ED%86%A0%EB%A6%AC/Main.java

devxb/JJUNalgo