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 | 2 | 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;
}
'ποΈ ICPC Sinchon > Dynamic Programming' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ][C++] λ°±μ€ 1904λ²: 01νμΌ (0) | 2024.08.25 |
---|---|
[BOJ][C++] λ°±μ€ 11722λ²: κ°μ₯ κΈ΄ κ°μνλ λΆλΆ μμ΄ (0) | 2024.08.19 |
[BOJ][C++] λ°±μ€ 1699λ²: μ κ³±μμ ν© (0) | 2024.08.14 |
[BOJ][C++] λ°±μ€ 8394λ²: μ μ (0) | 2024.08.14 |
[BOJ][C++] λ°±μ€ 2293λ²: λμ 1 (0) | 2023.11.24 |