문제 (English)
Starting in the top left corner of a $2 \times 2$grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many search routes are there through $20 \times 20$ grid?
Answer: 137846528820
문제 분석
Grid에 대해 (0,0) 포인트의 시작점에서 시작해서 (m,n) 지점까지 가는 경우의 수를 구하는 문제이다. 이동할 때는 가로로는 오른쪽으로, 세로로는 아래쪽으로 이동하면서.
다이내믹 프로그래밍으로 풀 수 있을 거다.
가로를 $x$축으로, 세로를 $y$로 놓고, 오른 방향을 $x$가 증가하는, 아랫 방향을 $y$가 증가하는 방향으로 놓고서, 각 지점에서의 이동할 수 있는 경우의 수를 C(x, y)로 놓고 풀면 되는.
또는, 이처럼 실제 Grid상의 지점을 이동하면서 경우의 수를 구하는 것이 아니라, 조합(Combination) 문제로 두고 풀 수도 있겠다.
풀이 1
다이내믹으로 풀어본다.
가로를 $x$축, 세로를 $y$로 놓자. 오른 방향이 $x$증가 방향, 아랫 방향이 $y$증가 방향
p(1,1)로 올 수 있는 방법은 p(1,0)과 p(0,1)에서 오는 방법뿐.
따라서, p(1,1)로 올 수 있는 경우의 수를 C(1,1)이라고 한다면, $C(1,1) = C(1,0) + C(0,1)$
일반화하면 $C(x,y) = C(x-1,y) + C(x, y-1)$
$C(1,1) = C(0,1) + C(1,0)$에서 C(0,1)과 C(1,0)의 값은 얼마일까?
$x=0$인 모든 점과 $y=0$인 모든 점에서의 C 값은 1이다.
p(2,0)으로 올 수 있는 경우의 수를 보면 $(0,0) \rightarrow (1,0) \rightarrow (2,0)$ 밖에 없기에 경우의 수는 1이다.
fn answer1(n:i32, m:i32) -> u64{
let mut g: Vec<Vec<u64>> = vec![vec![0; (m+1) as usize]; (n+1) as usize];
for i in 0..=n as usize { g[i][0] = 1;}
for j in 0..=m as usize { g[0][j] = 1;}
for i in 1..=n as usize {
for j in 1..=m as usize{
// g[i][j] = g[i-1][j] + g[i][j-1];
g[i][j] = (g[i-1][j] + g[i][j-1]) % 1000000007;
}
}
return g[n as usize][m as usize];
}
위 코드에서 1000000007로 나머지 연산을 했다. 이것은 hackerrank 사이트에서 이 수로 나머지 연산을 한 값을 요구하기 때문. euler project 사이트에서는 $20 \times 20$의 문제만을 요구하기에 u64로도 처리할 수 있는데, hackerrank에서는 $500 \times 500$ 문제까지 요구하고, 이 답은 매우 큰 수이기에 1000000007로 나눈 나머지만 답으로 출력하라고 되어 있다.
hackerrank에서 동작되는 코드는 아래와 같다.
use std::io::{self, BufRead};
fn main(){
let stdin = io::stdin();
let mut it = stdin.lock().lines();
let t = it.next().unwrap().unwrap().trim().parse::<i32>().unwrap();
for _ in 0..t {
let v:Vec<String> = it.next().unwrap().unwrap().trim().split(' ')
.map(|s| s.to_string()).collect();
let n = v[0].trim().parse::<i32>().unwrap();
let m = v[1].trim().parse::<i32>().unwrap();
println!("{}", answer1(n,m));
}
}
fn answer1(n:i32, m:i32) -> u64{
let mut g: Vec<Vec<u64>> = vec![vec![0; (m+1) as usize]; (n+1) as usize];
for i in 0..=n as usize { g[i][0] = 1;}
for j in 0..=m as usize { g[0][j] = 1;}
for i in 1..=n as usize {
for j in 1..=m as usize{
// g[i][j] = g[i-1][j] + g[i][j-1];
g[i][j] = (g[i-1][j] + g[i][j-1]) % 1000000007;
}
}
return g[n as usize][m as usize];
}
풀이 2
이 문제를 다이내믹이 아닌, 조합 공식에 의해 풀 수도 있다.
(0,0)에서 시작해서 (m, n)까지로의 경로를 생각해 보면, 어떤 경로를 택하더라도 x 축으로 m번 움직이고, y축으로 n번 움직이는 것은 변함이 없다.
$5 \times 5$ 격자에 대해 생각해 보자.
1번 경로를 표시해 보면 $(x1,y1,x2,y2,x3,y3,x4,y4,x5,y5)$. $x$가 5번 나왔고, $y$가 5번 나왔다.
2번 경로를 표시해보면 $(y1,y2,y3,x1,y4,x2,y5,x3,x4,x5)$. 역시 5번씩 나왔다.
즉, $x1$에서 $x5$까지 5개와, $y1$에서 $y5$까지 5개. 총 10개에 대해서 순서를 세우는 문제이다.
문제를 단순화하기 위해서 $x$축에 대해서만 생각해 보면, 총 10개의 자릿수에 대해서 5개의 $x$가 위치할 자리를 결정하는 문제이다. 이때 $y$는 생각할 필요가 없다. $x$가 결정되면 나머지 자리에 들어가는 y는 고려할 필요가 없다.
따라서, 이 문제는 조합(Combination) 문제이다.
n개에서 k의 조합 공식은 $C(n,k) = \frac {n!} {k!(n-k)!}$
따라서 $5 x 5$ 격자에 대한 경로수는 $C(10,5) = \frac {10!}{5!5!} = 252$
$m \times n$ 격자에 대해서 일반화해보자.
$C(m+n, m)$이 답이다. 이때 $C(m+n,n)$을 구해도 된다. 왜나면 둘 다 같은 값이기 때문
$C(m+n, m)$을 어떻게 구현할지 고민해 보자.
$C(m+n, m) = \frac {(m+n)!}{m!(m+n-m)!} = \frac {(m+n)!}{m!n!}$
여기서 $m>=n$ 이라고 한다면,
$\frac {(m+n)!}{m!n!} = \frac {(m+n)(m+n-1)...(n+1}{n!} = \frac {(n+1)(n+2)...(m+n-1)(m+n)}{(1)(2)...(n)} = \frac{n+1}{1} \frac{n+2}{2}...\frac{m+n}{n}$
코드로 구현하면 아래와 같다.
fn answer2(n:i32, m:i32) -> u64{
let mut large:u64 = n as u64;
let mut small:u64 = m as u64;
if m > n { large = m as u64; small=n as u64; }
let mut p:u64 = 1; //product
for i in 1..=small {
p *= large + i;
p /= i;
}
return p;
}
총평
다이내믹 문제이다. 단, 메모이제이션을 사용해야 속도가 나온다.
그냥 조합 문제로 풀어도 된다.
전체 소스코드
p15.rs
#[test]
fn test(){
assert_eq!(2, answer(1, 1));
assert_eq!(6, answer(2, 2));
assert_eq!(10, answer(3, 2));
assert_eq!(137846528820 % 1000000007, answer(20, 20));
assert_eq!(159835829, answer(500, 500));
}
#[cfg(test)]
use std::collections::HashMap;
#[cfg(test)]
fn answer(n:i32, m:i32) -> u64{
let mut cache:HashMap<(i32,i32), u64> = HashMap::new();
return path(n, m, &mut cache);
}
#[cfg(test)]
fn path(y:i32, x:i32, cache:&mut HashMap<(i32,i32), u64>) -> u64 {
match (x,y) {
(0,0) => return 0,
(0,_) => return 1,
(_,0) => return 1,
(_,_) => {
if let Some(val) = cache.get(&(x, y)) {
return *val;
}else{
let cnt = (path(x-1, y, cache) + path(x, y-1, cache)) % 1000000007;
cache.insert((x,y),cnt);
return cnt;
}
},
}
}
//-------------------------------
// 리스트 이용
#[test]
fn test1(){
assert_eq!(2, answer1(1, 1));
assert_eq!(6, answer1(2, 2));
assert_eq!(10, answer1(3, 2));
assert_eq!(137846528820 % 1000000007, answer1(20, 20));
assert_eq!(159835829, answer1(500, 500));
}
#[cfg(test)]
fn answer1(n:i32, m:i32) -> u64{
let mut g: Vec<Vec<u64>> = vec![vec![0; (m+1) as usize]; (n+1) as usize];
for i in 0..=n as usize { g[i][0] = 1;}
for j in 0..=m as usize { g[0][j] = 1;}
for i in 1..=n as usize {
for j in 1..=m as usize{
// g[i][j] = g[i-1][j] + g[i][j-1];
g[i][j] = (g[i-1][j] + g[i][j-1]) % 1000000007;
}
}
return g[n as usize][m as usize];
}
//-----------
// n+m개에서 m개를 고르는 문제
// C(m+n, m) = (m+n)! / m!(m+n-m)! = (m+n)!/m!n!, C(m+n,n) = (m+n)! / n!(m+n-n)! = (m+n)!/n!m!
// if m>=n, (m+n)!/m!n! = (m+n) * (m+n-1) * .. * (m+1) / n!
// m=3 n=2, 5*4/2*1
#[test]
fn test2(){
assert_eq!(2, answer2(1, 1));
assert_eq!(6, answer2(2, 2));
assert_eq!(10, answer2(3, 2));
assert_eq!(137846528820, answer2(20, 20));
assert_eq!(10, answer2(500, 500));
}
#[cfg(test)]
fn answer2(n:i32, m:i32) -> u64{
let mut large:u64 = n as u64;
let mut small:u64 = m as u64;
if m > n { large = m as u64; small=n as u64; }
let mut p:u64 = 1; //product
for i in 1..=small {
p *= large + i;
p /= i;
}
return p;
}
//---------
#[test]
fn test_cmp(){
for i in 1..=20 {
for j in 1..=20{
let a = answer2(i,j);
let b = answer1(i,j);
if a != b {
println!("i={}, j={}, answer2={}, answer1={}", i, j, a, b);
}
}
}
}
끝
'Programming > Rust로 Euler 문제 풀이' 카테고리의 다른 글
017. Number Letter Counts (숫자를 영어로 읽었을 때, 몇 개의 문자가 되는지 구하기) (5) | 2024.09.02 |
---|---|
016. Power Digit Sum ($2^{1000}$과 같은 큰 지수승 구하기) (0) | 2024.09.02 |
014. Longest Collatz Sequence(짝수이면 n/2, 홀수는 3n+1인 변환에서 1이될 때까지 몇 번 변환인지 구하기) (4) | 2024.09.02 |
013. Large sum (50자리 정수에 대한 덧셈 구하기) (0) | 2024.09.02 |
012. Highly divisible Triangular Number (약수의 개수가 k가 넘게되는 삼각수 구하기) (0) | 2024.09.02 |