1. Pancake Deque
deque에서 수를 꺼낼건데, 해당 수가 이전에 나왔던 수들 보다 크거나 같으면 cnt가 1 증가한다. 이때 최대 cnt를 구하는 문제다.
그리디하게 deque에서 꺼낼 때 front와 back중 작은 쪽을 꺼내고, 꺼내면서 이전 수보다 크거나 같으면 ans를 1증가시키면 된다. 설명할게 없다.
백준 기준 ~실버 예상
2. Controlled Inflation
$N$명의 사람이 각자 $P$개의 공을 갖고 있다. 펌프를 통해서 $P$개의 공에 정해진 양 만큼 공기를 넣어야한다. 공기를 넣는 기계는 -, +버튼으로 공기압을 1 감소시키거나 1 증가시킬 수 있다. $N$명의 사람은 앞 사람이 $P$개의 공에 공기를 다 넣을 때 까지 기다렸다가 순서대로 넣어야한다. 다만, 각 사람이 $P$개의 공에 공기를 넣는 순서는 상관없다.
공기압을 넣는 기계의 공기압이 0부터 시작할 때, 공기압 기계의 버튼을 누르는 횟수를 최소화 시키는 문제다.
조금 미안할 정도로 쉽다. 공은 순서를 바꾸어도 상관없으니 일단 정렬한다. 그리고 이전 사람이 마지막으로 세팅한 값을 그대로 받아서 사용하게 되므로 $i$번째 사람이 공기압을 넣을 때 $i - 1$번째 사람이 마지막으로 넣은 공의 공기압으로 부터 시작하게 된다. 따라서 DP테이블을 아래와 같이 정의할 수 있다.
$DP[i][j]$ : $i$번째 사람이 공기압을 넣을 때, 기계 세팅값이 $i - 1$번째 사람의 $(j == 0 ? 첫번째 : 마지막)$ 공의 공기압일 때 최소로 기계를 만지는 횟수
이렇게 정의하면 이전 기계의 상태가 같이 저장 되기 때문에 $i$번째 사람이 공기압을 넣을 때 기계를 움직이는 최소 횟수를 구할 수 있다. 넣어야 하는 공의 공기압 범위가 $[a_1,a_p]$이므로 이전 상태가 해당 범위 안에 있는지, 밖에 있는지에 따라서 케이스워킹해주면 된다.
WA를 한번 받았는데, 범위에 따른 케이스 분류를 안 해도 되는 줄 알고 그냥 갈겼다. 그리고 케이스 분류하는데 살짝 꼬여서 20분? 정도 더 걸려서 조금 아쉽다. 최소 10분은 단축할 수 있었는데.. ㅠㅠ
백준 기준 골드3 예상
3. ASeDatAb
1바이트 수만 저장할 수 있는 db에 숫자 하나($X$)가 저장되어 있다. db에 쿼리를 날릴 때 1바이트 수 $V$를 날릴 수 있는데, 쿼리를 날리면 $r$만큼 rightshift된 $W$가 db에 전달된다. 그리고 db에서는 응답으로 저장된 숫자와 xor연산을 하고, 그 결과($X xor W$)에서 비트 1의 개수를 리턴해준다.
최대 300번의 쿼리를 해서 저장된 숫자를 0으로 만드는 문제다.
또 Interaction문제다. 무지성으로 비트1의 개수만큼 1을 붙히고, 나머지는 전부 0으로 붙히는 방식으로 제출했는데 1번 tc를 ac받아버렸다. 2번 tc는 $X$와 $r$가 valid한 선에서 변한다는 것 같은데 정확하게 무슨 의도인지 모르겠다.
처음에 생각한 풀이는 비트가 8개밖에 없으므로 후보군을 전부 나열하고 지워가는 방식으로 해야하나? 생각했는데 $r$때문에 $W$를 예측할 수 없어서 포기했다.
지금 생각해보니 1번 tc는 그 $r$을 예측해서 푸는 것을 의도한 것 같고, 2번 tc는 $r$이 변하므로 "그게 불가능하니 다른 방법으로 풀어라" 같은데...
통과되긴 했는데 최근에 너무 실수도 많고 문제자체도 잘 못 푸는 것 같아서 많이 아쉽다. 확실히 퍼포먼스가 많이 떨어진 느낌이라 조금 착잡하다.
