BOJ Random Defense 3일차 (240527)

문제를 풀었다.

 

요약

 

13810. Futon (Gold I, 10:30)

 

PPC 기출인 이 문제와 비슷하다. 인접한 두 칸에 대해 만약 같은 Futon에 속한다면 다른 색 (머리-다리), 다른 Futon에 속한다면 같은 색 (머리-머리, 다리-다리) 로 칠해져야 한다. 이분 그래프 판별을 응용해 해결할 수 있다. 그래프가 조금 귀찮게 주어지는 점에 유의하자.

 

3037. 혼란 (Gold I, 8:10)

 

\(DP[i][j]\) 를 길이가 \(i\), inversion이 \(j\)개인 수열의 개수로 정의하자. 이러면 \(DP[i][j] = DP[i-1][j] + \cdots + DP[i-1][j-i+1]\)로 구할 수 있다. (\(i\)를 끼워넣는 위치에 따라 inversion의 증가량이 결정된다.) 이를 그대로 구현하면 TLE니 누적합 DP를 하나 더 만들어서 관리해주면 된다.

 

30921. N-Queen (Area) (Platinum VI, 7:32)

 

증명은 어렵지만 찍맞이 지나치게 쉬운 문제이다. 찍으면 맞는다. 대회 문제로는 좀 별로인 것 같다고 생각했다.

 

19571. 탐색 게임 (Gold I, 17:59)

 

결국 마지막 100개의 숫자가 대각선으로 배치되어 있어야 함을 유추할 수 있다. 이를 배치하고 나면 남은 9900개의 수로 path 비슷한 것을 만들면 된다. 아마 6*6 정도의 작은 사이즈를 먼저 만들어 본다면 어렵지 않게 구성할 수 있을 것이다.

 

1129. 키 (Platinum III, UPSOLVED)

 

이상한 사풀에 꽂혀서 삽질하다가 시간이 다 지났다. 끝나고 침착하게 생각해보니까 풀이가 잘 나와 반성해야겠다는 생각이 많이 들었다. 요새 뭔가 자꾸 하나에 꽂혀서 못 나오고 삽질하는 빈도가 는 것 같다는 생각이 든다. 팀 연습을 할 때에는 팀원들이 막말을 하며 잘 꺼내주는데, 이러다보니 마인드 자체가 좀 무뎌진게 아닌가 싶기도 하다.

 

첫 PASSED도 썼고, 당장 기말고사라는 급한 일을 처리해야 할 것 같아서 1주일 정도 쉬고 재개할 예정이다.