반응형

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

 

2253번: 점프

N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp [ i ][ j ]에서 i는 현재 돌의 번호, j는 x의 값입니다.

 

2. 다음과 같은 점화식을 세웁니다.

dp[ i ][ j ] = min(dp [ i ][ j ], go(i + xx, xx) + 1)

 

3. 2에서 xx는 j + 1, j - 1( > 0), j입니다.

 

[ 소스코드 ]

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
44
45
46
47
48
49
50
51
52
53
#include<iostream>
 
using namespace std;
 
int N, M;
int m[10001];
int dp[10001][150];
 
int go(int cur, int x)
{
    if (cur == N) return 0;
 
    int& ret = dp[cur][x];
    if (ret != 0) return ret;
    
    ret = 987654321;
 
    for (int i = -1; i < 2; i++) {
        int xx = x + i;
 
        if (xx > 0 && cur + xx <= N && m[cur + xx] != 1) {
            ret = min(ret, go(cur + xx, xx) + 1);
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int num;
        scanf("%d", &num);
 
        m[num] = 1;
 
        if (m[2] == 1) {
            printf("%d", -1);
            return 0;
        }
    }
 
    go(1, 0);
 
    if (dp[1][0] == 987654321) {
        printf("%d", -1);
    }
    else {
        printf("%d", dp[1][0]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 7569번 - 토마토 (C++)  (0) 2022.11.08
[ 백준 ] 2195번 - 문자열 복사 (C++)  (0) 2022.11.07
[ 백준 ] 14002번 - 가장 긴 증가하는 부분 수열 4 (C++)  (0) 2022.11.05
[ 백준 ] 1577번 - 도로의 개수 (C++)  (0) 2022.11.04
[ 백준 ] 2229번 - 조 짜기 (C++)  (0) 2022.11.03
반응형

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

 

1890번: 점프

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 재귀 함수를 통해서 각 좌표에서 갈 수 있는 좌표의 경로 개수를 모두 더해줍니다.

 

2. 정답의 범위가 int형을 벗어나므로 long long 자료형을 사용해줍니다.

 

3. 마지막에 dfs(0, 0)을 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[100][100];
int dy[2] = { 0,1 };
int dx[2] = { 1,0 };
long long dp[100][100];
 
long long dfs(int y, int x)
{
    if (dp[y][x] != 0) return dp[y][x];
    if (arr[y][x] == 0 && y != N - 1 && x != N - 1) {
        return 0;
    }
    if (y == N - 1 && x == N - 1) return 1;
 
    for (int i = 0; i < 2; i++) {
        int yy = y + dy[i]*arr[y][x];
        int xx = x + dx[i]*arr[y][x];
 
        if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
            dp[y][x] += dfs(yy, xx);
        }
    }
 
    return dp[y][x];
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    printf("%lld", dfs(0,0));
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1309번 - 동물원 (C++)  (0) 2022.10.30
[ 백준 ] 1965번 - 상자넣기 (C++)  (0) 2022.10.29
[ 백준 ] 9461번 - 파도반 수열 (C++)  (0) 2022.10.27
[ 백준 ] 2579번 - 계단 오르기 (C++)  (0) 2022.10.26
[ 백준 ] 2410번 - 2의 멱수의 합 (C++)  (0) 2022.10.25

+ Recent posts

티스토리툴바