반응형

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

 

5569번: 출근 경로

상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다.  남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[h][w][dir][turn] 배열을 만들어 해당 좌표에 해당 방향으로 방향을 바꿨는지 여부를 따져 도착할 수 있는 경우의 수를 저장합니다. (dir : 0 - 가로, 1 - 세로)

 

2. 다음과 같은 점화식을 이용하여 dp 배열을 채웁니다.

dp[ i ][ j ][ 0 ][ 0 ] = (dp[ i ][ j - 1 ][ 0 ][ 1 ] + dp[ i ][ j - 1 ][ 0 ][ 0 ]) % M;
dp[ i ][ j ][ 0 ][ 1 ] = dp[ i ][ j - 1 ][ 1 ][ 0 ] % M;
dp[ i ][ j ][ 1 ][ 0 ] = (dp[ i - 1 ][ j ][ 1 ][ 1 ] + dp[ i - 1 ][ j ][ 1 ][ 0 ]) % M;
dp[ i ][ j ][ 1 ][ 1 ] = dp[ i - 1 ][ j ][ 0 ][ 0 ] % M;

 

3. (dp[ h ][ w ][ 0 ][ 0 ] + dp[ h ][ w ][ 0 ][ 1 ] + dp[ h ][ w ][ 1 ][ 0 ] + dp[ h ][ w ][ 1 ][ 1 ]) % M 의 값을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#define M 100000
 
using namespace std;
 
int dp[101][101][2][2]; // h, w, dir, turn
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int w, h;
    cin >> w >> h;
 
    for (int i = 2; i <= w; i++) {
        dp[1][i][0][0] = 1;
    }
 
    for (int i = 2; i <= h; i++) {
        dp[i][1][1][0] = 1;
    }
 
    for (int i = 2; i <= h; i++) {
        for (int j = 2; j <= w; j++) {
            dp[i][j][0][0] = (dp[i][j - 1][0][1] + dp[i][j - 1][0][0]) % M;
            dp[i][j][0][1] = dp[i][j - 1][1][0] % M;
            dp[i][j][1][0] = (dp[i - 1][j][1][1] + dp[i - 1][j][1][0]) % M;
            dp[i][j][1][1] = dp[i - 1][j][0][0] % M;
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ans += dp[h][w][i][j];
        }
    }
 
    cout << ans % M;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 12016번 - 라운드 로빈 스케줄러 (C++)  (0) 2023.09.20
[ 백준 ] 17609번 - 회문 (C++)  (0) 2023.09.19
[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
[ 백준 ] 5549번 - 행성 탐사 (C++)  (0) 2023.09.15

+ Recent posts

티스토리툴바