[학습 5회차] 카카오 코드 페스티벌 문제 D문제 살펴보기

이번에는 카카오 코드 페스티벌 문제 D를 해결하기 이전에 문제를 살펴보고 팀원들과 토론하는 시간을 가졌다.

D문제의 제목은 '부스터'로 이전에 한 번 접해봤던 팀원의 말로는 이 문제 역시 union find를 사용해서 해결하는 문제라고 하였다. (정확하지는 않지만, 여러가지 해결 방법이 있는 것 같았다.) 우선, 매번 하는 것처럼 문제를 풀기 이전에 앞서 어떤 입력과 출력을 요구하는 문제인지를 살펴보았다.

 

[문제]

새로 출시된 게임의 세부 사항을 조정하고 있다. 다양한 스테이지의 개발을 위해 질의를 빠르게 처리해야하는데, 게임의 룰은 아래와 같다.

 

1. 이 게임은 2차원 평면 상에서 진행되는 게임이다.

2. N개의 체크포인트가 존재하며, 이 체크 포인트를 오가면서 원하는 곳에 도달하는 목표를 가진 게임이다.

3. 최대 HP는 X 만큼의 제한을 가지며, 부스터라는 기능이 있다. 

 

이동 방법은 두가지가 있다.

1. 걷기: 단순한 동작이며, 원하는 방향으로 걸어갈 수 있다. d만큼의 거리를 걸어갔을 때 체력도 d만큼 감소한다. 0미만이 되면 캐릭터는 죽는다.

2. 부스터: 네 가지 방향으로 선택가능하다. 서, 동은 각각 X좌표에서 움직이며 감소와 증가를 하고 북,남은 각각 Y좌표에서 움직이며 감소와 증가를 한다. 단, 이 때는 체력을 소모하지 않으며 부스터를 종료하면 그 자리에서 멈추게 된다.

 

-> 부스터는 사용 후 방전이 되며, 무조건 사용하기만 하면 방전 상태가 된다.

이를 충전할 수 있는 방법은 체크 포인트이며 체크 포인트에서 HP를 최대 한 번, 방전된 부스터를 최대 한 번 재충전이 가능하다.

 

위와 같으므로, 해결할 문제는 최대 HP제한이 X일때, 체크포인트 A에서 시작해서 체크포인트 B로 이동할 수 있는 방법이 있는지 없는지를 체크하면 되는 문제이다.

 

입력은 체크 포인트의 수 N, 질의의 수 Q가 주어진다.

만약 입력이 5 3 이라면 5개의 체크포인트 좌표를 입력하면 되는 것이고, 그 다음 x,y,z에 해당하는 질의를 3개 입력하면 된다. 여기서 x,y,z는 각각 x번 체크 포인트에서 y번 체크포인트로 최대 HP 제한 X의 상태에서 움직일 수 있는지 없는지를 나타내는 것이다. 여기서 이 질의가 가능한 것인지 아닌지를 Y와 N로 표시하면 된다.

 

https://www.acmicpc.net/problem/15955

15955번: 부스터

문제를 정리했지만, 솔직히 어떻게 풀지 감이 안온다.

다음 시간에 문제를 해결할 때는 정 감이 오지 않는다면 다른 사람의 코드 리뷰를 통해 문제를 해결하도록 해 볼 것이다.