8/25 Problem Solving

15961 회전 초밥 (G4)

 

슬라이딩 윈도우로 고정된 구간을 연속적으로 보면서 초밥 가짓수의 최댓값을 구한다. 쿠폰 사용 여부를 따로 변수로 둬서 누적해서 세는 경우가 없도록 했다.

 

http://boj.kr/07bfe0b8abf94fc99b0e67dd9e6f4a22

 

 

9011 순서 (G5)

 

R를 이용해서 S를 구하려면 R의 뒤에서부터 거꾸로 봐야지 원소들을 하나로 정할 수 있다. check 배열을 따로 둬서 현재 위치의 앞에 r[i]가 check 안되어있으면 s[i]를 정할 수 있다. 끝까지 봤는데도 아직 자리를 못찾으면 IMPOSSIBLE를 출력해준다.

 

http://boj.kr/c3d6b307fa5640e49d4b74a223c3f1cf

 

 

16985 Maaaaaaaaaze (G2)

 

판 하나당 4가지 경우로 나눠지고, 총 5개의 판이 있다. 그리고 5개의 판끼리 나열의 경우 5! 가지가 있다. 따라서 총 4^5*5! 가지에 대해서 브루트포스를 하면 된다. 각 경우에 대해서 BFS로 출발점부터 시작해서 도착점까지 갈 수 있는 확인해주면 된다.

 

http://boj.kr/d801de8681374ea79e85fb40c5096643

 

 

1461 도서관 (G4)

 

책이 0 위치에 있으므로 한번에 갈때 양수 위치끼리, 음수 위치끼리 처리하는게 이득이다. 양수, 음수 위치 각각에 대해서 가장 먼 위치부터 M개씩 처리해주면 된다. 마지막 책을 처리하고서는 다시 0으로 돌아올 필요가 없으므로 이 부분은 답에서 빼준다.

 

http://boj.kr/f50a37bdfc7d4599ba2b15558cf34fd4

 

 

8983 사냥꾼 (G4)

 

사대를 기준으로 생각하지말고 반대로 각 동물의 위치에서 생각해보자. 각 동물의 위치에서 x좌표 기준으로 가장 가까운 사대를 찾는다. lower_bound로 찾을 경우 이렇게 찾은 사대와 그 이전 사대에 한 군데라도 도달할 수 있는지 고려하면 된다. 기준 사대로부터 뒤의 사대를 고려할 필요가 없는 이유는 뒤의 사대는 적어도 x좌표가 크거나 같기 때문에 기준 사대가 안되면 뒤의 사대들은 전부 안되기 때문이다.

 

http://boj.kr/2845ac28e8cb4e6b9992d38a61c05d2d