특별하게 어렵거나 쉽다기보단... DP 쥐뿔도 모르는 내가 꾸역꾸역 풀어본 문제라서 올려봄


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
#include <iostream>
 
int dp[1000010];
 
int main()
{
    int input, N;
    int cnt = 0;
    std::cin >> input;
    dp[2] = dp[3] = 1;
    N = 4;
    while (N <= input)
    {
        if (N % 3 == 0)
        {
            if (dp[N - 1] >= dp[N / 3])
                dp[N] = dp[N / 3] + 1;
        }
        if (N % 2 == 0)
        {
            if (dp[N - 1] >= dp[N / 2])
            {
                if (dp[N] == 0)
                    dp[N] = dp[N / 2] + 1;
                else if(N % 3 == 0)
                    if(dp[N] > dp[N / 2])
                        dp[N] = dp[N / 2] + 1;
            }
        }
        if(dp[N] >= dp[N - 1] + 1 || dp[N] == 0)
            dp[N] = dp[N - 1] + 1;
        ++N;
    }
    int i = dp[input];
    std::cout << i;
    return 0;
}
cs


이건 겨우겨우 풀어댄 방법


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
int dp[1000010];
 
int main()
{
    int input, N;
    int cnt = 0;
    std::cin >> input;
    dp[2] = dp[3] = 1;
    for (int N = 4; N <= input; ++N)
    {
        dp[N] = dp[N - 1] + 1;
        if (N % 3 == 0)
            dp[N] = dp[N] > dp[N / 3] + 1 ? dp[N / 3] + 1 : dp[N];
        if (N % 2 == 0)
            dp[N] = dp[N] > dp[N / 2] + 1 ? dp[N / 2] + 1 : dp[N];
    }
    std::cout << dp[input];
 
    return 0;
}
cs


이건 훨씬 깔끔한 방법


DP의 핵심은, 반복문을 한큐에 끝낼 수 있는가


인듯.


브루트포스처럼 코드가 이리흐르고 저리흐르면 망한다는 것이다


그러기 위해선 이곳저곳으로 흘러흘러가는 코드보다는


처음부터 끝까지 우직하게 지나가는(저장하는) 방식이 동적배열에 더 맞지 않는가 싶다.



저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 2579: 계단 오르기(DP)  (0) 2019.08.14
백준 10814: 나이순 정렬 (병합 정렬)  (0) 2019.08.09

계단: 2579


피보나치: 1003


그래서 동적계획법은 대체 머 어케하는건데??했던 지난날보다는 성장했지만


여전히 약간 꼬아놓은 문제는 간단하게 풀어내기 힘들다.


간단하게 풀었던 다른 문제들에 비해

(피보나치 함수는 내가 쉽게 풀었던 것에 비해 정답률이 생각보다 낮아서.. 너무 좋았따...크큭....)


계단문제에서 주춤했다. 사실 똑같이 간단한 문제인데... 정답에 접근하는 방법도 거의 근접했는데


어느 순간 생각이 산으로 가버리고...


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
#define max(a,b)            (((a) > (b)) ? (a) : (b))
 
int dp[301];
int stair[301];
 
int main()
{
    int N = 0;
    std::cin >> N;
    std::cin >> stair[1] >> stair[2];
    dp[1] = stair[1];
    dp[2] = stair[1] + stair[2];
    for (int i = 3; i <= N; ++i)
    {
        std::cin >> stair[i];
        dp[i] = max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
    }
    std::cout << dp[N];
    return 0;
}
cs


코드를 짜면서도 '이렇게 풀면 될 것 같은데?' 하자마자


'음 아닌것같은데' (사실 정답이었다)




이건 개망한 접근방법

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
#include <iostream>
 
int dp[301];
 
int main()
{
    int N = 0;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> dp[i];
    }
    int sum = 0;
    --N;
    int i = 2;
    while(N >= 0)
    {
        sum += dp[N];
        if (i == 2)
        {
            i = dp[N - 1] > dp[N - 2] ? 1 : 2;
        }
        else if (i == 1)
        {
            i = 2;
        }
        N -= i;
    }
    std::cout << sum;
    return 0;
}
cs


개시발


저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22
백준 10844: 쉬운 계단 수(DP)  (0) 2019.08.19
백준 1463: 1로 만들기(DP)  (0) 2019.08.16
백준 10814: 나이순 정렬 (병합 정렬)  (0) 2019.08.09

+ Recent posts

티스토리툴바