Algorithm
📌 문제 정보 : 벚꽃 내리는 시대에 결투를
- 문제 분류 : 다이나믹 프로그래밍 (DP), 배낭문제
- 문제 출처 : 백준 골드 2, 벚꽃 내리는 시대에 결투를
✅ 접근 과정
문제에서 주어진 범위들(공격 횟수(N) <= 5000, 라이프(L) <= 5000, 오라(A) <= 10^9)을 보고 DP 아니면 그리디로 접근해야 겠다고 생각했다.
처음엔 마지막 공격부터 그리디로 접근했지만 오라 공격(X)과 라이프 공격(Y) 중 최선의 경우를 선택할 수 없어서 그리디가 틀렸다는 것을 깨닫고 DP로 접근했다.
수의 범위를 고려했을 때, 공격 횟수(N)과 라이프(L)을 기준으로 dp(i, j) = 최대 오라의 값을 가질 수 있도록 배낭 유형 방식으로 풀이를 했다.
그래서 실제 구현에서는 오라를 관리하기 위한 dp와 경로를 역추적하기 위한 path, 2개의 2차원 배열을 사용하여 구현했다.
유용했던 정보(보드게임컵 해설) : https://www.acmicpc.net/board/view/107887
✨ 풀이 코드
🚩 마치며
경로를 역추적하기 위해서 3차원 배열을 사용하기도 했고 2차원 배열에 경로를 "LALL"처럼 문자열로 쭉 나타내기도 했지만 모두 시간초과에 걸렸다..
이를 해결하기 위해 path 배열에 숫자값 하나만을 저장하여 역추적을 구현했다. 원시값 복사와 새로운 객체를 선언하는 것이 단순 숫자 하나를 저장하는 것보다 상당히 많은 비용이 든다는 것을 깨달은 문제였다.
이번 보드게임컵 7문제 해결을 목표로 도전했는데 이 문제를 시간 내에 풀지 못해서 결국 6문제로 마무리했다. 너무 아쉬웠지만 아직 실력이 많이 부족한 걸 느낄 수 있었다. 앞으로도 꾸준히 문제를 풀어야 겠다.
마무리로 이번 보드게임컵 보상 배경화면이다. 5문제 해결 보상이지만 생각보다 괜찮은 것 같다.
