생존과 탈출
시간 제한1초메모리 제한128 MB
시간 순서로 도착하는 상자마다 먹어서 HP를 올릴지 쌓아서 높이를 올릴지 선택해 최대한 오래 생존하면서 높이 D에 가장 빨리 도달하는 시점을 구하는 문제입니다.
문제
발을 헛디뎌 깊이 D인 함정에 빠졌다. 함정 안으로는 음식이 들어 있는 상자가 차례로 떨어진다. 상자 하나를 받으면 두 가지 중 하나만 선택할 수 있다. 내용물을 먹어 HP를 늘리거나, 먹지 않은 상자를 바닥에 쌓아 발판의 높이를 높이는 것이다. 상자를 비운 뒤에는 발판으로 쓸 수 없으므로, 같은 상자를 먹는 데 쓰고 쌓는 데에도 쓸 수는 없다.
시각 0에 HP 10으로 시작한다. 시간이 1 흐를 때마다 HP는 1 감소한다. HP가 0이 되는 바로 그 순간에 도착한 음식을 먹을 수 있다면 계속 생존할 수 있다. 주어진 상자들을 이용해 쌓은 높이가 D 이상이 되어 탈출할 수 있는 가장 이른 시각을 구하라.
입력
첫째 줄에 두 자연수 D와 G가 주어진다. D는 함정의 깊이이고, G는 던져지는 상자의 개수이다.
다음 G개의 줄에는 각 상자의 정보가 세 자연수 T, F, H로 주어진다. T는 상자가 던져지는 시각, F는 내용물을 먹었을 때 증가하는 HP, H는 상자를 쌓았을 때 증가하는 높이이다. 입력의 상자 정보는 시각순으로 정렬되어 있지 않을 수 있다.
출력
탈출할 수 있다면 탈출이 가능해지는 가장 이른 시각을 출력한다. 끝까지 탈출할 수 없다면 생존할 수 있는 최대 시각을 출력한다.
제한
- 1 <= D <= 100
- 1 <= G <= 100
- 1 <= T <= 1000
- 1 <= F <= 30
- 1 <= H <= 25
힌트
가능한 최적 선택 중 하나는 첫 번째 상자를 쌓아 높이 9를 만들고, 두 번째 상자는 먹어 생존 가능 시각을 13까지 늘리는 것이다. 세 번째 상자를 쌓으면 높이가 19가 되고, 네 번째 상자까지 쌓으면 높이가 20이 되어 탈출한다. 탈출 순간 HP가 0이라서 죽는다는 뜻은 아니다.