πŸ•οΈ ICPC Sinchon/Dynamic Programming

[BOJ][C++] λ°±μ€€ 10164번: κ²©μžμƒμ˜ 경둜

선달 2024. 8. 15. 02:53
λ°˜μ‘ν˜•

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

 

문제

ν–‰μ˜ μˆ˜κ°€ N이고 μ—΄μ˜ μˆ˜κ°€ M인 격자의 각 칸에 1λΆ€ν„° N×MκΉŒμ§€μ˜ λ²ˆν˜Έκ°€ 첫 ν–‰λΆ€ν„° μ‹œμž‘ν•˜μ—¬ μ°¨λ‘€λ‘œ λΆ€μ—¬λ˜μ–΄ μžˆλ‹€. 격자의 μ–΄λ–€ 칸은 β—‹ ν‘œμ‹œκ°€ λ˜μ–΄ μžˆλ‹€. (단, 1번 μΉΈκ³Ό N × M번 칸은 β—‹ ν‘œμ‹œκ°€ λ˜μ–΄ μžˆμ§€ μ•Šλ‹€. λ˜ν•œ, β—‹ ν‘œμ‹œκ°€ λ˜μ–΄ μžˆλŠ” 칸은 μ΅œλŒ€ ν•œ κ°œμ΄λ‹€. 즉, β—‹ ν‘œμ‹œκ°€ 된 칸이 없을 μˆ˜λ„ μžˆλ‹€.) 

ν–‰μ˜ μˆ˜κ°€ 3이고 μ—΄μ˜ μˆ˜κ°€ 5인 κ²©μžμ—μ„œ 각 칸에 λ²ˆν˜Έκ°€ 1λΆ€ν„° μ°¨λ‘€λŒ€λ‘œ λΆ€μ—¬λœ μ˜ˆκ°€ μ•„λž˜μ— μžˆλ‹€. 이 κ²©μžμ—μ„œλŠ” 8번 칸에 β—‹ ν‘œμ‹œκ°€ λ˜μ–΄ μžˆλ‹€.

 

격자의 1번 μΉΈμ—μ„œ μΆœλ°œν•œ μ–΄λ–€ λ‘œλ΄‡μ΄ μ•„λž˜μ˜ 두 쑰건을 λ§Œμ‘±ν•˜λ©΄μ„œ N×M번 칸으둜 κ°€κ³ μž ν•œλ‹€. 

  • 쑰건 1: λ‘œλ΄‡μ€ ν•œ λ²ˆμ— 였λ₯Έμͺ½μ— μΈμ ‘ν•œ μΉΈ λ˜λŠ” μ•„λž˜μ— μΈμ ‘ν•œ 칸으둜만 이동할 수 μžˆλ‹€. (즉, λŒ€κ°μ„  λ°©ν–₯μœΌλ‘œλŠ” 이동할 수 μ—†λ‹€.)
  • 쑰건 2: κ²©μžμ— β—‹λ‘œ ν‘œμ‹œλœ 칸이 μžˆλŠ” κ²½μš°μ—” λ‘œλ΄‡μ€ κ·Έ 칸을 λ°˜λ“œμ‹œ μ§€λ‚˜κ°€μ•Ό ν•œλ‹€. 

μœ„μ—μ„œ 보인 것과 같은 κ²©μžκ°€ μ£Όμ–΄μ§ˆ λ•Œ, λ‘œλ΄‡μ΄ 이동할 수 μžˆλŠ” μ„œλ‘œ λ‹€λ₯Έ 경둜의 두 가지 μ˜ˆκ°€ μ•„λž˜μ— μžˆλ‹€.

  • 1 → 2 → 3 → 8 → 9 → 10 → 15
  • 1 → 2 → 3 → 8 → 13 → 14 → 15

κ²©μžμ— κ΄€ν•œ 정보가 μ£Όμ–΄μ§ˆ λ•Œ λ‘œλ΄‡μ΄ μ•žμ—μ„œ μ„€λͺ…ν•œ 두 쑰건을 λ§Œμ‘±ν•˜λ©΄μ„œ 이동할 수 μžˆλŠ” μ„œλ‘œ λ‹€λ₯Έ κ²½λ‘œκ°€ 총 λͺ‡ κ°œλ‚˜ λ˜λŠ”μ§€ μ°ΎλŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜λΌ. 

μž…λ ₯

μž…λ ₯의 첫째 μ€„μ—λŠ” 격자의 ν–‰μ˜ μˆ˜μ™€ μ—΄μ˜ 수λ₯Ό λ‚˜νƒ€λ‚΄λŠ” 두 μ •μˆ˜ Nκ³Ό M(1 ≤ N, M ≤ 15), 그리고 β—‹λ‘œ ν‘œμ‹œλœ 칸의 번호λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜ K(K=0 λ˜λŠ” 1 < K < N×M)κ°€ μ°¨λ‘€λ‘œ 주어지며, 각 값은 곡백으둜 κ΅¬λΆ„λœλ‹€. K의 값이 0인 κ²½μš°λ„ μžˆλŠ”λ°, μ΄λŠ” β—‹λ‘œ ν‘œμ‹œλœ 칸이 μ—†μŒμ„ μ˜λ―Έν•œλ‹€. Nκ³Ό M이 λ™μ‹œμ— 1인 κ²½μš°λŠ” μ—†λ‹€.

좜λ ₯

주어진 격자의 정보λ₯Ό μ΄μš©ν•˜μ—¬ μ„€λͺ…ν•œ 쑰건을 λ§Œμ‘±ν•˜λŠ” μ„œλ‘œ λ‹€λ₯Έ 경둜의 수λ₯Ό κ³„μ‚°ν•˜μ—¬ 좜λ ₯ν•΄μ•Ό ν•œλ‹€. 

 

풀이

K번 칸을 μ§€λ‚˜κ°€λŠ” 경우의 μˆ˜λŠ”

첫번째 μΉΈμ—μ„œ k번 μΉΈκΉŒμ§€ κ°€λŠ” 경우의 수 * k번 μΉΈμ—μ„œ λ§ˆμ§€λ§‰ μΉΈκΉŒμ§€ κ°€λŠ” 경우의 수

이 λ‘˜μ˜ 곱으둜 λ‚˜νƒ€λ‚Ό 수 μžˆλ‹€.

 

쀑학ꡐ μˆ˜ν•™κ³Όμ •μ— μžˆλŠ” μ΅œλ‹¨ 경둜 μ°ΎκΈ° 문제 μœ ν˜•μ„ μ‘μš©ν•΄μ„œ

고등학ꡐ 확톡 경우의 수 단원에 λ‚˜μ˜€λŠ” μœ ν˜•μ΄ μžˆλŠ”λ° λ”± κ·Έκ±°λ‹€

 

νŠΉμ • μΉΈκΉŒμ§€ κ°€λŠ” 경우의 μˆ˜λŠ” dpλ₯Ό μ΄μš©ν•˜μ—¬ ꡬ할 수 μžˆλ‹€.

int ways(int n, int m) {
    vector<vector<int>>dp(n, vector<int>(m,1));
    
    for(int i=1; i<n; i++) {
        for(int j=1; j<m; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[n-1][m-1];
}

 

 

이제 k번 칸이 λͺ‡λ²ˆμ§Έ 쀄 λͺ‡λ²ˆμ§Έ 칸인지 μ•Œμ•„μ•Όν•œλ‹€

 

κ³„μ‚°μ˜ νŽΈμ˜μ„±μ„ μœ„ν•΄ 칸을 0λΆ€ν„° μ±„μš΄λ‹€κ³  κ°€μ •ν•˜μž

예λ₯Όλ“€μ–΄ n=3 m=5의 κ²½μš°μ— λ‹€μŒκ³Ό 같이 될 것이닀.

0  1 3 4
5 6 7 8 9
10 11 12 13 14

 

각 숫자λ₯Ό m으둜 λ‚˜λˆˆ λͺ«κ³Ό λ‚˜λ¨Έμ§€λ₯Ό κ΅¬ν•΄μ„œ {λͺ«, λ‚˜λ¨Έμ§€} ν˜•νƒœλ‘œ ν‘œν˜„ν•˜λ©΄

0,0 0,1 0,2 0,3 0,4
1,0 1,1 1,2 1,3 1,4
2,0 2,1 2,2 2,3 2,4

 

λͺ«μ€ ν–‰-1, λ‚˜λ¨Έμ§€λŠ” μ—΄-1 을 λ‚˜νƒ€λ‚΄λŠ” μˆ«μžλΌλŠ”κ±Έ μ•Œ 수 μžˆλ‹€

 

즉, kλ²ˆμ— ν•΄λ‹Ήν•˜λŠ” μ’Œν‘œλ₯Ό ꡬ할 수 μžˆλ‹€

    k--;
    int x = k/m + 1;
    int y = k%n + 1;

 

μ½”λ“œ

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

const int INF = 100001;

int ways(int n, int m) {
    vector<vector<int>>dp(n, vector<int>(m,1));
    
    for(int i=1; i<n; i++) {
        for(int j=1; j<m; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[n-1][m-1];
}

int solution(int n, int m, int k) {
    
    if(k==0) {
        return ways(n,m);
    }
    
    k--;
    int x = k/m + 1;
    int y = k%m + 1;
    
    int to_k = ways(x,y);
    int from_k = ways(n-x+1, m-y+1);

    return to_k * from_k;
}

int main() {
    int n,m,k;
    cin >> n >> m >> k;
    
    cout << solution(n,m,k);
    
    return 0;
}
λ°˜μ‘ν˜•