1. BOJ4641 Doubles
리스트에서 각 숫자의 순서가 아닌 개수만이 중요하므로, 리스트를 순회하여 개수를 기록하고, 모든 숫자를 set에 삽입한다. set을 순회하면서 $cnt[x]\times !!cnt[2\times x]$를 모두 합하면 끝.
2. BOJ18004 From A to B
얼핏 우박수와도 비슷해보이지만, 결정적인 차이점은 숫자가 줄어들거나 늘어나려면 한 가지 선택지밖에 없다는 것이다. A>B라면 A가 짝수인지를 고려해서 A:=A/2를 가능한 한 시행하고, A<=B라면 A+=1을 B-A번 시행하여 두 수를 같게 만들 수 있다.
3. BOJ20500 Ezreal 여눈부터 가네 ㅈㅈ
상당히 당황스러운 디스크립션의 문제지만(…), 아무튼 어렵지 않다.
$DP[i][j]$를 1, 5로만 구성된 $i$자리 숫자 중 15로 나눈 나머지가 $j$인 것으로 정의한다면, $DP[i+1][(j\times10+k) \mod 15]+=dp[i][j]$를 모든 $i$,$j$,$k$에 대해($k$는 1또는 5) 시행한다면 올바른 dp값을 얻을 수 있다.
4. BOJ2600 구슬게임
뭔가 딱 보고 답 생각 안 나면 대부분 dp나 이분탐색인 것 같다. 쉬운 dp 문제이다.
dp(a,b)를 “a,b개의 통이 남아있을 때 내 턴이라면 이길 수 있는가?”로 정의하자. 이때 두 가지 통에서 b1,b2,b3개 중 하나를 꺼냈을 때 상대가 항상 지는 경우의 수가 단 하나라도 있다면 이길 수 있으므로 이를 탑다운 dp로 짜면 간단하게 풀린다. b1,b2,b3이 같을 경우 dp(a,b)는 항상 동일하므로 dp table을 초기화하지 말고 5개의 쿼리에서 동일하게 사용하도록 하자. 또한, dp(a,b)=dp(b,a)임이 자명하므로 $a\le b$가 항상 성립하게 swap해주면 memoization 효율을 높일 수 있다.
5. BOJ16441 아기돼지와 늑대
전형적인 BFS/DFS 문제이다. 빙판에서 슬라이드하는거 구현만 실수 안하면 깔끔하게 풀린다.
6. BOJ2186 문자판
$DP[i][j][k]=(\text{현재 매칭한 글자가 }k\text{개이고 }(i,j)\text{에 있을 때 가능한 경로의 수})$
상태공간 $100\times100\times80=800,000$ 각 상태마다 최대 약 20번의 연산
대략 1600만번의 연산이면 충분하다. simple dp.
Endcard
solved.ac에서 alt+enter를 쓰면 쿼리문에 해당하는 문제 중 랜덤하게 하나를 바로 창으로 띄울 수 있다는 것을 처음 알게 되었다. 이걸로 위 세 문제를 골랐는데, 뭐… 다음과 같은 쿼리문을 썼지만 비교적 티어가 낮은 문제들이 뽑힌 것 같다. 미니멈 난이도를 좀 올려야 할 듯.
tier:b5..g1 -solved_by:$me solved:100..