Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
10164번: 격자상의 경로
입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으
www.acmicpc.net
풀이
간단한 DP문제로 간단한 점화식
dp[r][c] = dp[r-1][c] + dp[r][c-1] 으로 경로의 수를 계산할 수 있다.
k가 0인 경우와 아닌 경우만 나누어 k가 0이 아니라면 두 가지 문제로 분할해서 계산된 값들을 곱해주면 된다.
하지만 본인의 경우, 아래와 같은 실수로 애먹었다.
경유지인 행, 열 위치 계산을 아래와 같이 진행한다면 큰 오류가 발생한다.
int dest_row = k / M +1 , dest_col = k %M;
위와 같은 식은 문제의 예제와 같이
열의 수가 2 이상인 경우
dest_row = 8/5 +1 = 2
dest_col = 8%5 = 3
(2,3)의 위치가 알맞게 계산되지만
예제 입력이 아래와 같은 경우
5 1 3
이때 경유지인 3번 격자의 행, 열 위치는
dest_row = 3/1 +1 = 4
dest_col = 3%1 = 1
으로 잘못된 경우가 발생한다.
따라서 단순히 for문을 돌며 순서에 맞는 위치를 계산하는 방법으로 바꾸자 통과했다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.2491 - 수열 (C++) (0) | 2020.11.29 |
|---|---|
| [백준] No.1495 - 기타리스트 (C++) (0) | 2020.11.28 |
| [백준] No.1915 - 가장 큰 정사각형 (C++) (0) | 2020.11.13 |
| [백준] No.5557 - 1 학년 (C++) (0) | 2020.11.13 |
| [백준] No.1520 - 내리막 길 (C++) (0) | 2020.11.10 |