[백준 / BOJ] 12785 토쟁이의 등굣길

문제

출처 : www.acmicpc.net/problem/12785

12785번: 토쟁이의 등굣길

w*h그리드가 주어지고, 토스트집의 위치 y,x가 주어진다.

인하대학교에 다니는 토쟁이가 토스트집(x,y)을 지나서 (w,h)에 위치한 학교에 갈려할때, 최소 이동횟수를 구하는 문제다.

 

풀이

모든 경우를 다 탐색할경우 한 골목에서 선택할수있는 선택지가 2개, 골목길의 수가 40000개 이므로, 2^40000번 반복해서 시간초과가 난다.

dp를 써서 풀었다.

 

dp[y][x] = 최소이동으로 도달한 경우의수 의 형태로 저장해줬다.

 

토쟁이의 위치(1,1)에서 직선으로 가는경우,

(2,1) (3,1) (4,1) (5,1)... 

(1,2) (1,3) (1,4) (1,5)...

위 두가지 경우 dp테이블에 저장될값은 항상 1이다. (직선으로 가는게 항상 최소이므로)

 

1. 도달가능한 최소경로는 항상 (위 -> 아래), (왼쪽 -> 오른쪽) 두 가지이다 (다른길로 돌아오면 최소가 될수없음)

따라서 (y,x)로 올수있는 최소경로는 (y-1,x)에서 오는경우, (y,x-1)에서 오는경우 두 가지 인걸 알수있다.

 

2. 거리차가 1인지점으로 가는 최소경로는 항상 1가지이다. (한칸만 움직이면되므로)

 

1번과 2번을 종합하면, dp식은

dp[y][x] = dp[y-1][x] * 1 + dp[y][x-1] * 1

= dp[y-1][x] + dp[y][x] 가 되는걸 알수있다.

 

토쟁이의 집에서 토스트 집에 들리고 학교로 가는경우는 

토스트집에 도달한 경우의수 * 토스트집에서 학교로 가는 경우의수 가 된다.

 

그대로 구현해서 출력하면 답

 

스택 오버플로우를 조심해야하는데, 모듈러 연산말고도 

마지막에 토스트집에 도달한 경우의수 * 토스트집에서 학교로 가는 경우의수 를 구할때 1000006 * 1000006 가 되서 int범위를 벗어날수있다. 배열 크기를 int가 아닌 long long 이상으로 잡아줘야함...

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/12785%20%ED%86%A0%EC%9F%81%EC%9D%B4%EC%9D%98%20%EB%93%B1%EA%B5%A3%EA%B8%B8/main.cpp

devxb/JJUNalgo