[cpp 알고리즘] 백준 20152 Game Addiction

[백준] 20152 Game Addiction cpp 풀이

알고리즘: 수학, 다이나믹 프로그래밍(DP), 조합론

https://www.acmicpc.net/problem/20152

문제 요약

- 집의 좌표(H,H) 에서 PC 방의 좌표(N,N)가 주어진다.

- 좌표평면(x,y)에서 y>x인 곳은 갈 수 없다. 

- 집에서 PC방까지 경로의 개수를 구해야 한다. (단, 상하좌우 방향으로 이동할 수 있고 한 번 이동할 때 거리는 1이다. 또한 항상 최단 경로로 움직인다.)

풀이 정리

- 최단경로라는 말에 처음에는 bfs로 생각을 하다가, 뒤로 갈 수록 너무 많고 생각보다 규칙이 보여서 dp로 접근했다.

- 아래 사진처럼 예제들을 직접 따라 그려보면 어떻게 구하는지 바로 알 수 있다. (지금 보니까 집이랑 PC방 위치를 반대로 했다)

   dp[i][j] = dp[i-1][j] + dp[i][j-1] 의 점화식을 구할 수 있다.

- 집과 PC방의 위치 자체가 중요한 게 아니고, 그 차이가 중요하다!

백준 20152 풀이

C++ 코드

#include <iostream>
using namespace std;

int H, N;
long long dp[32][32]; // 최단거리 저장
long long ans = 0;

int main(){
    cin >> H >> N; //집 -> 피씨방
    
    if(H<N){
        int temp = H;
        H = N;
        N = temp;
    }
    else if(H==N){
        ans = 1;
		cout << ans;
		return 0;
    }
    
    if(H>N){
        dp[N][N] = 1;
        for(int i=N; i<=H; i++){ //y
            for(int j=N+1; j<=H; j++){ //x
                if(i>j) dp[i][j] = 0;
                else dp[i][j] = (i > N ? dp[i-1][j] : 0) + (j > N ? dp[i][j-1] : 0);
            }
        }
        ans = dp[H][H];
    }
    
    cout << ans;
    return 0;
}

20%에서 틀렸습니다

- 0 30 을 입력해보니까, 음수의 값이 나와서 int 범위를 벗어나는 걸 확인했다 => long long 으로 고쳐주었다.

24%에서 틀렸습니다

- i나 j가 N혹은 H범위를 벗어날 때는 처리해주지 않아서 그런거였다...

=> N의 값을 벗어날 때는 0으로 처리해 주었다. 

 

그리고, 중간에서 틀렸습니다가 나오면 입/출력도 뿐만 아니라 type의 범위와 배열들의 범위를 다시 한번 확인해 봐야겠다.

=> 특히 끝 값들이 잘 처리가 되고 있는지...