백준

문제 링크 (2024/9/13 기준) Gold V 문제 읽기 문제가 살짝 난해합니다; $1$초부터 $T$초까지 매 초 $1$번 나무 또는 $2$번 나무에서 하나씩, 총 $T$개의 자두가 떨어집니다. $W$번 이하로 이동하며 떨어지는 자두를 받았을 때의 최댓값을 구해봅시다. 처음 시작은 $1$번 나무입니다. 풀이 제한을 잘 살펴봅시다. $T \leq 1 000$, $W \leq 30$, 나무가 $2$그루 있으니, dp[현재 시간][현재 위치][현재까지 이동한 횟수]로 3차원 DP를 해볼 수 있을 것 같습니다. 우선, DP 테이블에 초깃값들을 채워봅시다. $t$초에 자두가 떨어진 나무의 위치를 $P_t$라고 하면, $1$초에 $1$번 나무에서 시작하니, $DP_{1, 1, 0}=[P_i = 1]$이 되겠고 (편의상 $[c]$는 조건 $c$가 참이면 $1$, 거짓이면 $0$ 값을 가진다고 약속합시다), $1$초에 자두가 떨어지기 전 $2$번 나무로 움직였다면, $DP_{1, 2, 1}=[P_i = 2]$가 됩니다....

문제 링크 (2024/9/12 기준) Silver I 문제 읽기 $N$명의 사람들이 일렬로 서 있습니다. 왼쪽에서 $i$ (단, $1 \leq i < N$)번째 사람까지는 홍팀, 나머지는 청팀으로, 총 $N-1$가지 방법으로 팀을 나눌 수 있습니다. 이때, 각 팀에서 힘이 가장 센 사람이 힘을 겨루어, 두 사람 중 힘이 더 센 사람이 포함된 팀이 승리하게 됩니다. (무승부일 때는 어느 팀도 승리하지 않습니다.) 둘 중 어느 팀이 승리할 확률이 더 높을까요? 풀이 일단, 전체 경우의 수는 $N-1$로 고정되어 있습니다....

문제 링크 (2024/9/10 기준) Gold III 문제 읽기 하노이 탑 변형 문제입니다. 대신 기둥 D가 추가되었고, 기둥 D에 한 번 옮기면 다시 뺄 수 없습니다. 이외에는 기존 하노이 탑과 규칙이 동일합니다. $N$개의 원판을 기둥 D에 옮기는 최소 이동 횟수와, 그러한 이동 방법을 하나 찾아봅시다. 예시 편의를 위해 초기 상태에서의 위로부터 $N$번째 원판을 원판 $N$이라고 하겠습니다. $N=2$일 때, A에 있는 원판 $1$을 B로 옮긴다. A에 있는 원판 $2$를 D로 옮긴다. B에 있는 원판 $1$을 D로 옮긴다....

문제 링크 (2024/9/9 기준) Gold III 문제 읽기 꽃이 $N$종류 주어집니다. 각각의 꽃은 피는 날과 지는 날이 각각 $MM\ DD$꼴로 주어지고, 최소한의 종류의 꽃으로 $3$월 $1$일부터 $11$월 $31$일까지 매일 적어도 한 종류의 꽃이 피어있도록 배치해봅시다. 단, $d$일에 꽃이 지는 경우, $d$일에는 꽃이 피어있지 않았음에 유의합시다. 예시 4 1 1 5 31 1 1 6 30 5 15 8 31 6 10 12 10 예제 1입니다. $4$종류의 꽃이 주어졌고, 이 중 $1$월 $1$일부터 $6$월 $30$일까지 피는 꽃과, $6$월 $10$일부터 $12$월 $10$일에 지는 꽃 $2$개를 선택하여 조건을 만족시킬 수 있습니다....

문제 링크 (2024/9/10 기준) Gold V 문제 읽기 $1$부터 $N$까지의 자연수를 색칠해야 합니다. 단, 서로소인 두 자연수는 서로 다른 색으로 칠해야 하고, 최소한의 색을 사용해야 합니다. 예시 $n=5$일 때, $1\ 2\ 3\ 4\ 5$를 $\color{salmon}1\ \color{sandybrown}2\ \color{seagreen}3\ \color{sandybrown}4\ \color{skyblue}5$로 $4$가지 색을 이용하여 색칠할 수 있습니다. 따라서, 정답은 $1\ 2\ 3\ 2\ 4$입니다. (색의 순서는 상관이 없습니다. 최소 개수를 만족하기만 한다면 정답으로 인정됩니다. 또한, $6$을 $2$와 같은 색으로 칠하든 $3$과 같은 색으로 칠하든 모두 정답으로 인정됩니다....