반응형

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

+ Recent posts

티스토리툴바