1, 5, 10, 20 ,100 단위의 지폐가 있다. 지불해야할 돈을 딱 맞게 지출 하는 최소 지폐 수를 구하는 문제다.
greedy하게 100짜리를 쓸 수 있으면 100짜리를 모두 쓰고 20짜리를 쓸 수 있으면 20짜리를 모두 쓰고 하면 된다.
총 $n$개의 줄이 있고 그 줄에 서 있는 사람 수가 주어진다. 매 초 마다 모든 줄에 한 명 씩 들어가게 되고, 0명이 되면 그 초에 경기장에 들어 갈 수 있다. 나는 줄을 조금 특이한 방식으로 설 건데, 먼저, 첫 번째 줄에 선 뒤, 매 초 마다 그 줄에서 경기장에 들어갈 수 없으면 바로 오른쪽 줄로 옮긴다. 즉, 그 줄의 사람수가 0이면 바로 들어갈 수 있으니 그 줄로 들어가지만, 아니면 오른쪽 줄로 옮긴다. 가장 오른쪽 줄에 있으면 다시 첫 번째 줄로 온다. 이런 방식으로 설 때, 몇 번째 줄을 통해 경기장에 들어가는지 구하는 문제다.
매 줄 마다 $a_i$명이 있으면 $n * k + i ( >= a_i)$초에 그 줄에 서면 그 줄에 들어가게 될 것이다. 따라서 각 줄 마다 가장 작은 $n * k + i ( >= a_i)$을 구하면 된다.
설명은 엄청 쉽지만 꽤나 오래 삽질한 문제다. 처음엔 줄이 짧은 순서대로 정렬한 뒤, 각 줄이 0이 되는 순간에 자신의 위치와 그 전의 자신의 위치 사이에 0이 있으면 거기로 들어가는 방식으로 구현했는데 구현이 상당히 어려웠다. 한 바퀴 돌아서 다시 원래 위치로 돌아오는 경우도 있고, 아니면 아예 앞으로 안 가는 경우도 있어서 처리가 까다로웠다.
개인적으로 b번중에 가장 어려운 문제.
주차장이 row가 4, column이 $n$으로 이루어져있다. 0과 3번째 row에는 차를 대는 자리이고, 1과 2번째 row에는 차가 지나다니는 자리이다. 차를 대는 자리에는 지정된 자동차 외에는 다른 차가 잠시라도 그 자리에 댈 수 없고, 자리가 지정된 자리 외의 자리에는 꼬깔콘이 세워져있어 아예 들어가지를 못 한다. 따라서 1, 2번째 row에만 차가 자유롭게 지나다닐 수 있다. 매 움직임 마다 하나의 차를 인접한 공간 한 곳으로만 움직일 수 있고, 한 공간에 두 대의 차가 들어가지 못 한다. 각 차의 위치가 주어져있을때, 200,000번 이하로 움직여서 모든 차를 지정된 자리에 주차할 수 있으면 차를 움직인 횟수와 차가 움직인 경로를 출력하고, 200,000번 이하로 주차하지 못 하거나 아예 주차하지 못 하는 경우는 -1을 출력하는 문제다.
움직일 수 있는 도로를 컨베이어벨트처럼 보면 컨베이어벨트를 총 $2n$번 움직이면 다시 처음 원래의 상태로 돌아올 것이다. 따라서, 처음 들어온 입력을 보고, 주차공간 바로 앞에 있으면 바로 주차공간에 넣어주고, 컨베이어 벨트를 한칸 움직이고 다시 주차공간 바로 앞에 있는애들을 주차공간에 넣어주는 연산을 총 $2n$번 반복하면될것이다. 한번 회전에 $2n$, 총 $2n$번 회전, 총 $k$개가 주차공간에 들어가므로 총 $4 * n^2 + k$번 즉, 10100번 움직임 이내로 모든 차들이 각자의 주차공간에들어갈 수 있다.
그런데 만약 $k == 2n$이라서 모든 움직일 수 있는 도로가 꽉차 있는데 주차공간 바로 앞에 있는 차가 없어서 주차공간에 차를 못 넣어준다면 더 이상 절대 움직일 수가 없으므로 결과는 -1이 될것이다. 그 외에는 무조건 10100번 이내로 모든 차를 주차할 수 있으므로 -1인 경우는 없다.
정말 신박한 문제다. 푼 사람 수만 봐도 얼마나 사람들이 고통받았는지 한 눈에 알 수 있다. c보다 d를 많이 풀었으니 말이다. div1이라고 사정이 다른것도 아니다. 그 만큼 생각하기 어렵지만 그 만큼 신박했던 문제다.
여담으로 row가 2인 배열로 도로를 회전시키면 회전구현이 정말 빡시다. 그냥 컨베이어벨트를 한 쪽에서 끊어서 쭉 연결시키듯이 해서 1차원 배열로 만들어서 처리하는게 더 간단할 수도 있겠다(아직 해보진 않았다.)
== 추가 ==
해보니 덜 복잡하긴 하지만 획기적으로 와 간단하다 하는건 아니다. 직관적인 방법인 2차원배열이 더 낫겠다.
파티에 총 $n$쌍의 커플이, 즉, $2n$명이 참석했다. 파티의 마지막에 기념사진을 찍기위해 커플끼리 세워서 사진을 찍고싶다. 그러기 위해서 지금 사람들이 서 있는 위치에서 인접한 두 사람의 위치를 서로 바꿀 수 있다. 지금 각 위치에 서 있는 사람들이 주어질 때, 각 커플끼리 인접하게 서 있게 만들기 위해 최소한으로 두 사람의 위치를 바꾸고싶다. 그 최소값을 구하는 문제다.
그냥 제일 왼쪽에 붙어 있는 사람에게 짝을 찾아서 붙여주고, index 2에 있는 사람에게 짝을 찾아서 index3에 붙여주고, index4에 있는 사람에게 짝을 찾아서 index5에 붙여주고.. 하는 식으로 greedy하게 하면 해결된다. 왜 그렇냐면 그렇기 때문이다. greedy는 정말로 설명을 못 하겠다.
b나 c보다 훨씬 쉬웠던 문제. 전체적으로 난이도 조절이 살짝 부족했던것 같다.
E번을 풀려고 정말 노력했는데 도저히 tutorial도 이해가 안 가고 다른사람들 코드도 이해가 안 간다. 중간에 엄청 greedy하게 푼 사람의 코드를 봐서 같은 방식으로 greedy하게 짰는데 계속 26번 tc에서 WA가 떠서 그 사람 코드에서 딱 한줄 빼고 똑같이 짯는데도 틀리길래 그 한줄 바꿔보니 AC가 나왔다. 그런데 그 한줄이 for문을 n - 1에서 0까지 도느냐 0부터 n - 1까지 도느냐 이기때문에 이상해서 tc만들어보니 문제의 tc가 부족했던것이다. 즉 틀려야할 코드가 맞다고 처리된 경우.. virtual뿐만아니라 실제 contest에서도 이렇게 푼 사람이 통과됬으니 조금 문제가 많은 contest인 것같다.
