Codeforces #574 (div 2) 후기

http://codeforces.com/contest/1195

불러오는 중입니다...

A. 최대 [n/2]개의 set이 있고 각 set은 drink가 2개씩 있다는 내용인데 문제 내용 자체는 이해하기 어려웠지만, 논리자체는 쉬웠다. 일단 모든 숫자의 갯수를 count한 뒤 count값을 2로 나눈 몫을 다 더해주고, 이게 n/2과 다르면 n/2과의 차만큼 drink를 더 선택할 수 있어서 그걸 더해주면 끝이다.

B. 지난번 수학문제(방정식 전개하는거)랑 비슷한 문제 양식이다. 나는 그냥 put하는 횟수가 y번이면 y(y+1)/2개의 캔디가 들어가고, eat을 x번 하면 k개의 캔디가 남아있다 했으니 y(y+1)/2 - x = k(x + y = n) 이 식을 y에 대해서 풀어준 뒤(x로 풀면 복잡) n-y를 해주면 x가 되는 것을 이용해서 구했다. 이 때 y에 대한 2차 방정식이 나오는데 y값이 음수가 되지 않으려면 +가 되는 값만 가능하므로 실질적으로 나올 수 있는 x는 두 개 중에서 항상 작은 값만 취해도 문제가 없다.

C. 농구 문제. 그냥 보자마자 이건 DP다. 라는 생각이 들어서 DP 식으로 접근해서 풀었다. 그림만 보면 어려운데 사실 논리는 전형적인 쉬운 DP문제다. 2차원 배열로 DP[0][i] = 0번째 line의 i번째 학생이 선택되는 경우, max height, DP[1][i] = 1번째 line의 i번째 학생이 선택되는 경우 이런 식으로 나눈 뒤, 다음의 점화식을 이용하면 된다.

DP[0][i] = max(DP[1][i-1], DP[1][i-2]) + height[0][i]

DP[1][i] = max(DP[0][i-1], DP[0][i-2]) + height[1][i]

식 자체는 간단하다. 그 전의 사람과 그 전전 사람을 둘 다 체크해야 하는데 그 전전전 사람(i-3번째)의 max값은 체크하지 않아도 되는 이유는 DP[0][i-3] < DP[0][i-3] + height[1][i-2] + height[0][i-1] <= DP[0][i-1]이라서 어차피 DP[0][i-1]에 포함되니까 그 앞부터는 고려하지 않아도 된다.

D. 이건 보면서 절대 O(n^2)으로 풀지 말라는 의미 같아서 다른 방법을 구해보려고 노력했다. 모든 숫자가 자릿수가 같아서 할 수 있는 풀이 방법을 생각해봤는데 전체의 합을 이용하면 좀 더 간단하게 더할 수 있다. 숫자의 digit을 다 나열해서 더한 후 식을 정리하면 규칙을 발견할 수 있다. 각각의 자릿수마다 n개의 숫자들의 i번째 digit들의 합을 이용하면 된다. 이 합에다 11, 1100, 110000을 곱한 후 n을 곱한 게 우리가 원하는 답이 된다. 나는 이걸 11, 1100, 110000 이런식으로 더하려 할때 10^19까지 이걸 pow를 이용해서 구해서 더했는데 그러면 overflow가 난다.ㅠㅠ pow 함수가 double을 인자로 받는 데 10^15까지는 문제가 없겠지만, 10^19까지는 문제가 발생할 수 있기 때문. 11, 1100이런식으로 11에 100씩 곱하고 %mod하면 문제가 발생하지 않는다.

 

[후기]

오늘은!!! 경사가 있는 날이다. 사실상 4문제를 푼 날이다!!!(물론 마지막 한 문제는 오버플로우가 나서 친구가 도와줬다. 이거만 해결하고 바로 accept됬으니 사실상 4문제로 인정해주자.) 행복하다. 친구도 잘 했다고 칭찬해줬다. 어쨋든 죽이 됬든 밥이 됬든 거의 매주마다 div2 열리면 거의 항상 했었는데 일단 꾸준히 하면 실력이 느는 것 같기도 하다. 물론 Codeforce 시스템이나 문제 출제 방식에 익숙해진 것도 큰 것 같다. 매주 이러지 말아야지,, 하는 피드백이 있어서 그거에 따라 점점 문제 푸는 실력도 좋아진 듯. 이번주의 피드백은 "overflow 조심하기" 이다. 그리고 문제 생각하기 전에 코딩부터 하려고 하는 습관이나, 어떤 알고리즘을 짤 지 생각해볼 때 시간복잡도를 생각하지 않고 이렇게 짜보면 되지 않을까?하면서 그냥 막무가내로 O(n^2) 알고리즘을 생각해내는 버릇을 고쳐나가고 있는데 이것도 도움이 많이 된 것 같다. 어쨋든 조금씩 좋아지는 걸 보니 굉장히 뿌듯하다. 다음 번 코포도 화이팅이다!

아무튼 등급도 뉴비에서 퍼필로 복귀했다. ㅠㅠ 뉴비 탈출,, 행복하다.