문제링크 : https://www.acmicpc.net/problem/1309


문제 접근

  • 어떻게 해야하는지 감이 안오는데? 우선 각 케이스를 구해보자
    • 2 X 0 : 0마리 1
    • 2 X 1 : 0마리 1, 1마리 2
    • 2 X 2 : 0마리 1, 1마리 4, 2마리 2
    • 2 X 3 : 0마리 1, 1마리 6, 2마리 8, 3마리 2
  • 다음 우리의 개수와 이전 우리의 개수의 연관관계 찾을때, 사자가 인접하지 않는다는 조건 때문에 복잡
    • 첫째줄에 사자가 없는경우, 왼쪽에 있는경우, 오른쪽에 있는 경우로 나누면 어떨까 >> 케이스별 2차원 DP
    • DP[N][0] = 2XN 타일 중 첫번쨰 줄에 사자 없는경우 = DP[N-1][0] + DP[N-1][1] + DP[N-1][2]
    • DP[N][1] =2XN 타일 중 첫번쨰 줄의 왼쪽에 사자 있는경우 = DP[N-1][0] + DP[N-1][2]
    • DP[N][2] =2XN 타일 중 첫번쨰 줄의 오른쪽에 사자 있는경우 = DP[N-1][0] + DP[N-1][1]
  • 초기조건
    • DP[0][0] = 1, DP[0][1] = 0, DP[0][2]= 0
    • DP[1][0] = DP[0][0] + DP[0][1] + DP[0][2] = 1
    • DP[1][1] = DP[0][0] + DP[0][2] = 1
    • DP[1][2] = DP[0][0] + DP[0][1] = 1
  • 사자가 없는 경우의수는 DP[0][0] 에 포함되며, 이후에도 계속 포함되서 계산됨

시간복잡도 계산

  • N칸에서 3번 계산 해줘야함, O(3*N), 3e5

인트 계산

  • 경우의수 9901 나머지 이므로 인트 범위 가능

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
using namespace std;
 
int dp[100010][3];
int main() {
    int N; cin >> N;
    fill(&dp[0][0], &dp[100009][3], 0);
    
    dp[0][0] = 1;
    for(int j=1; j<=N; j++) {
        dp[j][0] = (dp[j-1][0] + dp[j-1][1] + dp[j-1][2]) %9901;
        dp[j][1] = (dp[j-1][0] + dp[j-1][2]) %9901;
        dp[j][2] = (dp[j-1][0] + dp[j-1][1]) %9901;
    }
    
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) %9901 << '\n';
    
    return 0;
}
 
cs

문제유형

  • 케이스별 2차원 DP
    • 각 케이스로 쪼개서 DP를 계산
    • 조건이 조금 복잡하다 싶으면, 이 유형인지 한번 확인 필요

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1744 수 묶기 쉬운 풀이(C++/CPP)  (0) 2021.02.06
백준 1963 소수 경로  (0) 2021.02.06
백준 1890 점프 쉬운 풀이(C++/CPP)  (0) 2021.02.06
백준 2225 합분해 쉬운 풀이  (0) 2021.02.06
백준 1520 내리막길 쉬운 풀이(C++/CPP)  (0) 2021.02.04

문제링크 : https://www.acmicpc.net/problem/1890

문제 접근

  • 이전의 경우의 수가 다음것에 바로 사용됨 >> DP
  • DP
    • 3이라고 적혀있는 칸일경우, 3칸 오른쪽이나 아래쪽에 값을 반영 가능할까? >> 가능할것 같음
    • DP[Y][X] = Y,X칸을 갈 수 있는 경우의 수
    • DP[0][0] = 1; , DP[0][0]의 값이 K일경우
    • DP[K][0] += DP[0][0], DP[0][K] += DP[0][0]

시간복잡도 계산

  • 가로 * 세로 >> O(N^2) >> 1e4

인트 계산

  • 모두 갈수 있는 경우라면 >> 2^100 >> 1e30 >> 인트 초과 >> DP값은 long long 사용

코드

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
#include <iostream>
 
using namespace std;
typedef long long ll;
 
ll dp[110][110];
int map[110][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            cin >> map[j][i];
        }
    }
    
    fill(&dp[0][0], &dp[109][110], 0);
    dp[0][0] = 1;
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            int k = map[j][i];
            if(k==0) continue;
            dp[j+k][i] += dp[j][i];
            dp[j][i+k] += dp[j][i];
        }
    }
    
    cout << dp[N-1][N-1]<< '\n';
    
    return 0;
}
 
cs

문제유형

  • 일반 DP

'알고리즘 > 백준' 카테고리의 다른 글

백준 1744 수 묶기 쉬운 풀이(C++/CPP)  (0) 2021.02.06
백준 1963 소수 경로  (0) 2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP)  (0) 2021.02.06
백준 2225 합분해 쉬운 풀이  (0) 2021.02.06
백준 1520 내리막길 쉬운 풀이(C++/CPP)  (0) 2021.02.04

문제링크 : https://www.acmicpc.net/problem/2225

문제 접근

  • 감이 안오는데? 각 케이스를 생각해보자

    • 20 = 19 + 1, 18+2, 17+3
    • 만약 K가 3일경우엔, 20 = 18+1+1, 17+1+2, 17+2+1, ...
    • 이전 값을 다시 재활용해서 사용할 수 있을것 같음 >> DP로 해보자 >> 종류 2차원 DP 문제
      • DP[K][N] = K개를 사용해서 N을 구하기 위해서 경우의 수
    • 앞에는 1개로 정해놓고 뒤에만 움직이는경우
      • DP[K][N] = DP[1][0] +DP[K-1][N] + DP[1][1] + DP[K-1][N-1] + DP[1][2] + DP[1][K-2] + ...
    • 근데 어짜피 K가 1이면 DP[1][K] = 1
    • DP[K][N] = DP[K-1][0] + DP[K-1][1] + DP[K-1][2] + ...DP[K-1][N]
    • 이때 예외가 있을까?
      • K = 1일때는 적용 안됨, 항상 종류 1
        ### 시간복잡도 계산

  • DP[N][K]에서 연산횟수 >> N-1번, 약 N번이라고 가정시

    • O(N_K_N) = O(N^2 * K) = 8e6 >> 가능
      ### 인트 계산

  • dp값을 1e9 나머지로 계산해줘서 신경써줄 필요없음
    ### 코드

    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
    #include <iostream>
     
    using namespace std;
    int dp[210][210];
    int main() {
        int N,K;
        cin >> N >> K;
        fill(&dp[0][0], &dp[209][210], 0);
        dp[0][0]= 1;
        // K=1 일경우 경우의수 1개 >> 각 수를 내서 만들수 있으니까
        fill(&dp[1][0], &dp[1][210], 1);
        
        for(int j=2; j<=K; j++) {
            for(int i=0; i<=N; i++) {
                for(int k=0; k<=i; k++) {
                    dp[j][i] = (dp[j][i] + dp[j-1][k]) % 1000000000;
                }
                
            }
        }
        
        cout << dp[K][N] << '\n';
        
        
        return 0;
    }
     
    		cs

문제유형

  • DP - 이전 종류값 만을 포함
    • dp[N][K] = N개의 종류를 가지고있을때, K가치를 가질때의 dp 값
    • 단, 이전값만을 활용하는경우, dp[N]으로 줄여서 사용할 수 있음
      • 단 한번만 빼줘야함, 뺀곳에 여러번 뺀 경우의 수가 담겨있음
    • 대표문제 : knapsack
      • 여러 종류의 아이템을 한번씩 넣을수있을때, 한정된 비용에서의 최대가치 구하는 문제
      • dp[N][K] : N개의 종류를 들고, K만큼의 무게에서의 가질수 있는 최대 가치
      • https://www.acmicpc.net/problem/12865

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1744 수 묶기 쉬운 풀이(C++/CPP)  (0) 2021.02.06
백준 1963 소수 경로  (0) 2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP)  (0) 2021.02.06
백준 1890 점프 쉬운 풀이(C++/CPP)  (0) 2021.02.06
백준 1520 내리막길 쉬운 풀이(C++/CPP)  (0) 2021.02.04

+ Recent posts

티스토리툴바