BOJ 1006 습격자 초라기
1006. 습격자 초라기 (Platinum III) 습격자 초라기는 복잡한 case work이 가미된 원형 DP 문제로 잘 알려져 있고, 웬만한 그리디 풀이는 사풀이며 반례가 반드시 존재한다는 것이 상식이었다. 그러나 오늘 pyb1031님이 PS갤러리에 그리디로 AC를 받은 코드를 인증했다. 즉시 스트레스 테스트를 돌려봤지만 반례가 나오지 않았고, 좀 더 생각해 본 결과 맞는 풀이라는 확신이 들었다. 이 글에서는 이 풀이가 무엇을 하는지, 왜 맞는지를 다룬다. ...
BOJ 11855 Bank
11855. Bank (Platinum II) 은행에 $m$장의 지폐가 있다. 각 지폐의 가치는 $b_1, b_2, \cdots, b_m$이다. 이 지폐들을 가지고 $n$명의 사람들에게 각각 $a_1, a_2, \cdots, a_n$만큼의 돈을 지급할 수 있는지 판별하시오. ...
BOJ 30563 Fast Forward
30563. Fast Forward (Platinum IV) $n$개의 노래의 길이가 주어진다. 광고를 마지막으로 본지 $c$시간이 지나면 다음 광고가 나오는데, $c$시간이 지났을 때 어떤 노래가 재생되고 있다면 그 노래가 끝난 후에 광고가 나온다. 모든 $1 \le i \le n$에 대해 $i$번째 노래부터 시작하여 $n$곡을 순서대로 모두 들었을 때 ($n$번째 노래 다음에는 $1$번째 노래로 돌아와서 계속 듣는다) 보게 될 광고의 개수를 모두 구하시오. 첫 곡을 재생하기 직전에 광고를 봤다고 가정하고, 첫 곡 직전과 마지막 곡 직후의 광고는 세지 않는다. ...
BOJ 13027 Clique Problem
13027. Clique Problem (Gold II -> Platinum V 기여) x축 위에 $N$개의 점이 있다. 각 점은 좌표 $x_i$와 가중치 $w_i$를 갖는다. 두 점의 가중치의 합이 두 점 사이의 거리 이하일 때 간선으로 연결한 그래프에서 maximum clique의 크기를 구하시오. ...
BOJ 32034 동전 쌍 뒤집기
32034. 동전 쌍 뒤집기 (Gold I ~ Platinum V) UCPC 2024 예선에 출제한 문제이다. 검수 과정에서 아주 다양한 풀이가 등장하여 이 글에서 모두 공유해보고자 한다. ...
BOJ 29149 A→B
29149. A→B (Platinum II) 길이가 $N$이고 정확히 $M$개의 1을 포함하는 binary string에서 시작하여, 001 → 110과 100 → 011의 조작만을 사용하여 0을 1개만 남기고 모두 1로 만들려고 한다. 시작 시에 두 1이 이웃하면 안된다. 이것이 가능한지 판별하고, 가능하다면 그러한 binary string을 아무거나 하나 찾아서 출력하시오. ...
BOJ 31684 Bitovi
31684. Bitovi (Platinum IV) $0$ 이상 $2^{15}$ 미만의 서로 다른 정수 $N$개로 이루어진 집합 $A$와 $B$가 주어진다. 한 번의 조작으로 $A$의 원소를 하나 골라 비트를 하나 변경할 수 있는데, 그 결과가 $A$에 이미 있는 값이면 안된다. $2^{19}$회 이하의 조작으로 $A$를 $B$로 바꾸는 방법을 하나 찾아 출력하시오. ...
BOJ 14379, 14380 BFFs
14379. BFFs (Small) (Silver I) 14380. BFFs (Large) (Gold I) $1$번부터 $N$번까지 $N$명의 아이들이 있다. 각 아이는 자기자신이 아닌 “베프"가 한 명씩 있다. 아이들 중 몇 명을 골라 원을 이루도록 앉혔을 때 원에 앉은 모든 아이의 바로 옆에 그 아이의 베프가 있도록 하고 싶다. 원에 앉을 수 있는 아이들의 수의 최댓값을 구하시오. ...
BOJ 14367, 14368 Fashion Police
14367. Fashion Police (Small) (Silver II -> Gold III 기여) 14368. Fashion Police (Large) (Platinum IV) $A, B, C$와 $k$가 주어질 때, 서로 다른 순서쌍 $(a, b, c)$ ($1 \le a \le A, 1 \le b \le B, 1 \le c \le C$)를 최대한 많이 고르는데, 같은 $(a, b)$, $(b, c)$, $(a, c)$의 조합을 $k$번 이하로만 사용할 수 있다. 예를 들어, $(1, 2, 3)$과 $(1, 2, 2)$를 고르면 $(a=1, b=2)$는 두 번, $(a=1, c=2)$는 한 번 사용한 것이다. ...
BOJ 25461 NMABCD, 9021 숫자 퍼즐, 27693 Grid travel
25461. NMABCD (Platinum I -> Diamond II 기여) 9021. 숫자 퍼즐 (Diamond II) 27693. Grid travel (Unrated -> Diamond I 기여) 모두 $N \times M$ 사각 격자판에서 $(A, B)$에서 $(C, D)$로 가는 최장 경로가 방문하는 칸의 개수, 또는 최장 경로를 아무거나 하나 구하는 문제이다. ...