문제링크
풀이방법
풀이 방법이 두 가지이다! 두 방법 모두 작성하고자 한다.
풀이 #1
간단한 수학식을 이용한 방법이다. 초기값이자 최대 생명력이 방을 통과할 때마다 바뀌는데, 그 차이를 diff라는 변수에 저장했다. 예를 들어,
3 3
1 1 20
2 3 10
1 3 100
이런 입력이 들어온다면, 초기에 diff = 0이었다가, 첫번째 방을 지나며 diff -= 1 * 6이 되는 것이다! 문제 내에 용사의 생명력은 그 최대 값을 초과할 수 없다고 되어있어서 힐을 받았을 때 그 때 diff가 0보다 큰지 확인하고 0 보다 크면 0으로 설정해 준다. 모든 방을 지나며 diff 값을 이런 방식으로 갱신해 주는 것이다! 그리고 (최대생명력값 + diff) >= 1 조건을 마지막에 적용해 최대생명력값을 얻는다. 하지만! 여기서 또 고려해야 할 게 있다! 예를 들어, diff가 -60까지 갔다가 힐을 받아 -10까지 되었다고 생각해보자. 위 식만 고려하면 최대생명력값을 11로 얻게된다. 그럼 -60이 된 시점에 이미 용사는 죽을텐데..? 그래서 diff에 마이너스 연산이 될 때 마다 최소 diff 값을 min 변수에 갱신한다. 그리고 수식을 (최대생명력값 + Math.min(diff, min)) >= 1로 변경해 적용하면 답을 얻을 수 있다.
코드
static void solution_expression() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long attack = sc.nextInt();
Queue<Room> rooms = new LinkedList<>();
while (--n >= 0) {
rooms.offer(new Room(sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
long diff = 0;
long min = 0;
while (!rooms.isEmpty()) {
Room currentRoom = rooms.poll();
if (currentRoom.type == MONSTER) {
int time = (int) Math.ceil((double) currentRoom.heal / attack);
diff -= currentRoom.attack * (time - 1);
if (min > diff) min = diff;
} else {
attack += currentRoom.attack;
diff += currentRoom.heal;
if (diff > 0) diff = 0;
}
}
min = Math.min(diff, min);
System.out.print((-1 * min) + 1);
}풀이 #2
이분탐색을 이용한 풀이 방법이다. 어떤 수가 용사의 생명력이 될 수 있는지 확인하는 데에는 O(n)밖에 소요되지 않고 이분탐색은 O(logn)의 시간복잡도를 갖기 때문에 충분한 시간복잡도를 갖게 된다! begin에는 용사의 생명력이 될 수 없는 값 중 최대값을 저장하고 end에는 용사의 최소생명력을 저장했다. begin, end를 계속 갱신하며 그 차이를 줄이다가 두 수가 연속한 수가 되면 end를 출력한다 !! 초기 begin 값은 0, end 값은 Long.MAX_VALUE로 설정했다.
코드
static void solution_binarySearch() {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long attack = sc.nextInt();
LinkedList<Room> rooms = new LinkedList<>();
while (--n >= 0) {
rooms.add(new Room(sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
long begin = 0;
long end = Long.MAX_VALUE;
while ((end - begin) > 1) {
long mid = (begin + end) / 2;
if (isValidHP(rooms, attack, mid)) end = mid;
else begin = mid;
}
System.out.print(end);
}
static boolean isValidHP(LinkedList<Room> rooms, long attack, long maxHP) {
long hp = maxHP;
for (Room room : rooms) {
if (room.type == MONSTER) {
int time = (int) Math.ceil((double) room.heal / attack);
hp -= room.attack * (time - 1);
if (hp <= 0) return false;
} else {
attack += room.attack;
hp += room.heal;
if (hp > maxHP) hp = maxHP;
}
}
return true;
}+) 풀이 #1의 경우엔 방 정보를 한 번만 사용하면 돼서 방을 차례로 간다는 그 의미를 바로 설명할 수 있는 Queue 자료구조를 이용했다. 풀이 #2에서는 방 정보를 계속해서 써야했기 때문에 LinkedList 자료구조를 이용했다.
