[백준 / BOJ] 2096 내려가기

문제

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

2096번: 내려가기

내려가기 게임을 하고있다. 이 게임은 첫번째 줄에서 마지막 줄까지 내려가는 게임인데, 내려갈때 일정한 규칙에 따라 내려가야한다.

 

바로 아래 칸으로 내려가거나 바로 아래칸에 연결된 칸으로만 내려갈수있다.

예를들어, 왼쪽에서 내려갈수있는경우는, 왼쪽아래와 가운데 아래이다.

 

마지막 줄까지 내려갔을때, 최댓값과 최솟값을 구하는 문제다.

 

풀이

N이 100000이라서 완전탐색으로 풀경우 시간초과가 난다. 그리디로 풀려고해도 현재까지 최대인값이 나중에 최소가 될수있으므로, 빠르게 모든경우를 봐주기위해 다이나믹 프로그래밍으로 풀어야하는 문제였다.

 

처음 문제를 봤을때는 전형적인 dp문제인줄알고 풀었다가 메모리 초과를 받았다.

문제를 보면, 메모리값이 4MB이라서 배열범위를 10만까지 늘릴수없기때문에 약간 변형해서 풀어야한다.

 

탐색과정에서, 3가지 경로를 비교하며 dp값을 업데이트하는데,

1. 현재 위치가 왼쪽일때, 왼쪽에서 내려오는경우와 중간에서 내려오는경우

2. 현재 위치가 중간일때, 왼쪽에서 내려오는경우, 중간에서 내려오는경우, 오른쪽에서 내려오는경우

3. 현재위치가 오른쪽일때, 중간에서 내려오는경우, 오른쪽에서 내려오는경우

 

위 경로를 보면 알아야할 값이 이전 idx인걸 알수있다. 즉 이전 idx값을 알고있다면, 배열의 크기를 N만큼 늘리지않더라도, 문제를 풀수있다.

탐색할때, i가 증가하는 값이 홀,짝,홀,짝 으로 증가하므로 dp배열의 크기를 3으로 잡고 문제를 풀었다.

 

구현은 간단한데, (i는 입력받은 횟수이다. N만큼 입력받음)

1. 현재 i가 홀수일때, dp[짝수]위치에서 위 에서 말한 3가지 경로를 비교해준다.

2. 현재 i가 짝수일때, dp[홀수]위치에서 위 에서 말한 3가지 경로를 비교해준다.

 

최댓값 최솟값모두 위와같은 방법으로 구하면 답이나온다.

 

(요즘 코드 이쁘게 짜는 연습하고있는데 생각대로 안된다...)

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2096%20%EB%82%B4%EB%A0%A4%EA%B0%80%EA%B8%B0/main.cpp

devxb/JJUNalgo