문제 (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 배열의 최솟값을 출력했다.
[소스코드]
'ALGORITHM > BOJ' 카테고리의 다른 글
| [BOJ] 1253번 좋다 (C++) (0) | 2022.01.19 |
|---|---|
| [BOJ] 3078번 좋은 친구 (C++) (0) | 2022.01.19 |
| [BOJ] 2211번 네트워크 복구 (C++) (0) | 2022.01.17 |
| [BOJ] 13549번 숨바꼭질 3 (C++) (0) | 2022.01.17 |
| [BOJ] 1238번 파티 (C++) (0) | 2022.01.17 |