ALGORITHM/BOJ
[BOJ] 2096번 내려가기 (C++)
yegyeom
2022. 1. 19. 15:41
문제 (https://www.acmicpc.net/problem/2096)
2096번: 내려가기
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
www.acmicpc.net
DP + 슬라이딩 윈도우로 해결한 문제이다. 두 알고리즘 모두 취약해서...ㅎㅎ 다른 코드를 참고하여 풀었다.
크기가 3인 배열들 minArr, maxArr, minTmp, maxTmp을 사용했는데, minTmp, maxTmp는 현재 행 이전까지의 결과를 저장해둔 배열이다.
- 첫 번째 행의 값들은 최솟값이자 최댓값이므로 4개의 배열에 모두 삽입해준다.
- 첫 번째 행이 아닐 경우에는 minTmp, maxTmp에 저장되어있는 이전 행까지의 결과를 사용하여 minArr, maxArr에 현재 행까지의 계산 결과를 저장한다.
- 다음 행으로 넘어가기 전에 minArr, maxArr에 존재하는 값들을 minTmp, maxTmp에 동일하게 넣어준다. (다음 행에서 현재 행까지의 결과를 사용할 수 있도록!)
- n번 반복이 끝나면 max_element와 min_element로 maxArr 배열의 최댓값과 minArr 배열의 최솟값을 출력했다.
[소스코드]
