크게 만들기 - 2812
무조건 앞의 숫자가 커져야한다.
앞에서부터 스택의 마지막 요소보다 큰 숫자들을 K번 제거한다.
과제 - 13904
순회강연 - 2109
문제의 소재 자체는 매우 자주 나온다. 하지만 난이도가 정확히 측정되지 않은 모양이다.
G4, G3, G2에서 다 본적이 있다.
13904 과제 문제를 기준으로 설명한다. (예제 1번)
처음을 1일날 이라고 해보자. 각 날마다 수행할 수 있는 과제를 나열해보자
| 날 | 수행할 수 있는 과제 점수 |
|---|---|
| 1일 | 60 40 20 50 30 10 5 |
| 2일 | 60 40 50 10 5 |
| 3일 | 60 40 10 5 |
| 4일 | 5 |
| 5일 | 5 |
당연하지만, 1일에서 5일로 넘어가는 동안, 수행가능한 과제의 개수는 줄어든다.
즉, 첫날에 5점을 얻는 과제를 해버린다면, 5일에는 어떤 과제도 수행할 수 없다.
때문에, 선택할 수 있는 과제가 제일 적은 5일부터 점수를 가장 많이 주는 과제를 선택해야한다.
어차피 그 전날들은 다른 선택권들이 있기 떄문이다.
200년간 폐관수련했더니 PS 최강자가 된 건에 대하여 - 19582
19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여
결정문제의 일종이다.
차례대로 대회를 참가하다가 참가할 수 없는 대회가 생긴 경우에 할 수 있는 2가지 행동이 있다.
-
이전에 참가했던 대회 중 하나를 취소해서 상금을 적게한 후 다음 대회에 참가한다.
-
대회를 참가하지 않고 뛰어넘는다
두 행동을 모두 해봐도 O(2N)으로 시간초과 나지 않으므로 모두 진행해서 풀었으나,
그럴 필요가 없다. 더 간단한 방법이 있다.
만약 1번행동을 해서 상금을 적게했는데도 다음 대회에 참가할 수 없다면 2번행동을 무조건해야한다.
만약 아니라면, 두 행동 중 상금을 더 적게 가지고 있는 경우만 생각하고 나머지 경우는 생각하지 않아도 된다.
공주님의 정원 - 2457
피울 수 있는 꽃중 꽃이 최대한 늦게 지는 꽃을 선택한다.
줄 세우기 - 7570
연속되지 않는 숫자를 앞이나 뒤로 보내서 연속되는 수열의 길이를 1씩 늘릴 수 있다.
즉, 숫자가 연속되는 수열의 최대 길이를 찾은 후 전체 길이에서 뺀다.
박스 채우기 - 1493
큰 박스의 길이는 작은 박스의 정수배이므로
가능하면 큰 박스부터 쌓기 시작한다.
2원 5개 쓰느니 10원 1개 쓰는것과 같은논리다.
당근 훔쳐 먹기 - 18234
토끼가 T일 동안 어떤 당근을 매일 먹었다고 하면, 그 당근으로 얻는 맛의 합은 T*w가 된다.
만약 그 당근을 T일 중 (앞에서부터) N일 먹지않았다고 하면, 그 당근으로 얻는 맛의 합은 (T-N)w + Np가 된다.
p > w 이므로 우항이 더 커질 수 밖에 없고,
결론적으로 N일 먹지 않았을 때의 최대합이 더 크거나 같다.
또한 N이 커질수록 그 차이는 커진다.
때문에 우리는 당근 하나를 고려했을 때, 가장 마지막날에 한번 먹어야 합이 최대가 된다.
이제 당근이 여러개가 있다고 해보자.
당근 세개가 있다고 했을 때, 영양제는 각각 p1 < p2 < p3이다.
각각 연속으로 당근을 묵힌 일 수를 a, b, c 라고 하면 각각의 합은
w1 + ap1, w2 + bp2, w3 + c*p3이고
우리가 구하는 값은 저 세가지 값의 합이 된다.
이때, 제일 큰값에 제일 큰값을 곱해야 제일 큰값이 되므로
c > b > a일 때, 합이 최대가 된다.
결론적으로 당근을 묵히는 일 수를 최대로 해야한다.
동시에, 하루에 한 당근만 먹을 수 있으므로 p가 가장 작은 당근부터 먹어주면 되겠다.
1082 방 번호
// 작성예정 //
1132 - 합
G4(단어수학)문제에서 0의 처리때문에 까다로워진 문제.
0이 될수 없는 후보들 중 가장 작은 알파벳을 0으로 선택한 후.
원래 알던것처럼 풀면된다.