[BOJ 24229] 백준 24229번 - 모두싸인 출근길

		2021 경인지역 6개대학 연합 프로그래밍 경시대회 shake! 풀이
A		[BOJ 24228] 젓가락
B		[BOJ 24229] 모두싸인 출근길
C		[BOJ 24230] 트리 색칠하기
D		[BOJ 24231] 해석
E		[BOJ 24232] 망가진 나무

1. 문제

$24229$. 모두싸인 출근길 (2021 경인지역 6개대학 연합 프로그래밍 경시대회 shake! Open Contest B번)

백준 24229번 - 모두싸인 출근길 (https://www.acmicpc.net/problem/24229)

2. 풀이

서로 연결되는 여러 개의 판자는 하나의 판자로 간주할 수 있다. 따라서, 겹치는 판자들을 하나로 이어주는 작업을 먼저 한다.

작업을 마치고 나면, 서로 $1$칸 이상 떨어져 있는 판자들이 왼쪽부터 순서대로 나열되어 있는 상태이다. 이를 처음부터 탐색하면서 지금까지 탐색한 판자들을 사용해서 점프해서 도달할 수 있는 최대 거리를 계산한다.

점프해서 도달할 수 있는 최대 거리 내에 이번 판자가 포함된다면, 해당 거리와 이번 판자에서 점프해서 갈 수 있는 최대 거리의 최댓값으로 최대 거리를 갱신한다.

1. 단순히 인접한 두 판자를 확인하여 연결하는 식으로 작업하면 오류가 생긴다.

예제 $2$에서 볼 수 있듯이 $11\sim 15$에서 $16\sim 17$로 점프가 가능하여 점프하게 되면, $19\sim 20$으로 가지 못하게 된다. 여기서는 $11\sim 15$에서 바로 $19\sim 20$으로 점프해야 한다. 이를 해결하기 위해 지금까지의 최대 점프 가능 거리를 저장하는 방식을 채용한다.

1. 최종 정답은 최대 점프 가능 거리가 아니라 도달한 마지막 판자의 오른쪽 좌표이다.

최대 점프 가능 거리는 해당 위치에 판자의 존재 여부와는 상관이 없다. 이는 다음 판자에 도달 가능한지를 확인하기 위한 수단일 뿐이다. 따라서, 도달한 판자의 index를 저장하는 작업이 추가로 필요하고, 도달한 마지막 판자의 오른쪽 좌표가 최종 정답이 된다.

3. 채점 결과

4. 회고

.

5. 코드