[2일차] Codeforces Round #377 (Div. 2)

 

결과는 이렇다.

 

A. Buy a Shovel (-, 00:03)

단순한 브루트 포스이다. 이때 i=1부터 n*i을 10으로 나누었을 때 나머지가 0이나 r면 그게 답이다.

답이 얼마 안되므로 상수 시간 안에 해결 할 수 있다.

코드

 

B. Cormen - The Best Friend Of a Man (-, 00:08)

인접한 두 칸을 더하면서, 만약 그게 k보다 작다면 뒷칸을 인접한 두 칸의 합이 k와 같게 만든다.

뒷칸을 증가시키는 건 다음 두 칸을 볼 때 그 두 칸의 합에 영향을 미치기에 그렇다.

이건 O(n)으로 구할 수 있다.

코드

 

C. Sanatorium (-, 00:32)

내가 푼 방식은 원래 이렇지 않지만, 끝나고 찾은 풀이가 훨씬 간단하기에 이 풀이를 쓸 것이다.

m = max(b,d,s)라고 정의한다면,

답은 max(m-1-b, 0)+max(m-1-d, 0)+max(m-1-s, 0)이다.

답이 왜 이렇게 나오는지는 b,d,s 중에서 m이랑 같게 설정할 변수들을 정해 캐이스를 만들고 그림을 그려서 확인해보길 바란다. (다른 캐이스가 7개 정도 나오므로 최대 7번 해보면 이해가 갈 것이다.)

O(1)만에 풀 수 있다.

코드

 

D. Exams (-1, 01:13)

우리는 이 문제를 "n일 있으면 모든 시험을 통과할 수 있는가?"라는 결정 문제로 환원하여 문제를 풀 것이다.

이는 결정 문제를 만족하는 자연수 n이 연속적으로 나오므로 Paramatric Search로 풀 수 있다.

이가 만족하는지 확인하는 건, 1일부터 n일까지 보면서 각 과목들에서 가장 늦게 있는 시험을 본다고 하고 그 시험들을 제외한 나머지 일들을 다 공부시간으로 바꾼다. 이렇게 해서 되는지 공부시간을 이용해서 시험을 패스할 수 있는지 판별해주면 된다.

판별은 O(m)만에 해줄 수 있고, 이분탐색은 O(log n)만큼 걸리므로 전체 시간복잡도는 O(m log n)이다.

코드

 

E는 업솔빙을 하면 블로그에 올릴 예정이다.

 

하고 나서.

이번엔 퍼플 퍼포가 나왔다. 기뻤지만 이번 D까지 문제가 쉬운데다가 E도 쉬웠는데 문제 이해를 계속 못하는 바람에 풀지 못했던게 너무 아쉬웠다. 

해보니까 진짜 뇌절을 거의 안하니까 이렇게 잘 뚫리는 것 같다. 물론 문제가 쉬웠던 탓도 있겠지만, 쉬운 문제를 뇌절하지 않았기에 이러한 결과가 나오지 않았나 싶다.

그러니까 뇌절 안하는 것을 항상 중요하게 여기고, 뇌절을 안하도록 노력하자.