구사과

(2017.9.26 : 초판)(2017.9.30 : J번을 제외한 모든 문제의 풀이를 추가했습니다. 블로그에 LaTeX 조판을 설치했고, G번 문제 풀이를 시험적으로 전부 LaTeX 수식으로 변경했습니다. J번 문제를 포함해서 앞으로 올라오는 글들은 모두 다 예쁘게 조판되어서 올라갈 예정이에요!)(2017.9.30 : J번의 풀이가 추가되었습니다.) Scoreboard잘해서 좋당 ㅋㅋ Problems / Solution sketch대충 난이도 순으로 정렬했다. 사실 5번째부터 10번째까지는 이견이 있을 수도 있고 나도 잘 모르겠지만 (…) 푼 사람 수와 개인적인 의견 등을 감안하여 적당히 정렬했다.마음에 들었던 문제는 D / G / J였다. B도 풀이가 상당히 재미있다.K. RegistrationH. M..

1. 도어맨굉장히 간단한 O(N) 그리디 풀이도 있는 거 같은데 난 잘 모르겠어서 DP로 해결했다. DP[i] = (1 ~ i번 사람이 모두 럽에 들어갔을 때 더 넣을 수 있는 사람의 수) 라고 정의하자. 두가지 케이스가 있다. * 첫번째 사람을 클럽에 영영 안 넣고 두번째 사람부터만 계속 추가. 이 방법으로 K명이 추가로 들어갔다면 DP[i] = K가 가능해진다. * 두번째 사람 이후를 K번 정도 더 넣고, 첫번째 사람을 추가. 차이에 문제가 생기지 않는다면 DP[i] = DP[i + K + 1] + K + 1가 가능해 진다. 모든 K에 대해서 대충 시뮬레이션한 후, 시뮬레이션 과정에서 문제가 없었으면 값을 갱신해주면 된다. 이런 식으로 DP 테이블을 채우면 DP[0]이 답이 된다. 잘 구현하면 O(N..

1. 지뢰찾기디스크립션에 매우 중요한 내용이 누락되어 있는데, 외곽선만 숫자가 공개되어 있으며 외곽선이 아닌 부분은 숫자가 전혀 써져있지 않다. 고로 외곽선과 붙어있는 영역에만 지뢰가 있을 수도 없을 수도 있는 것이고, 그렇지 않은 n-4 * n-4 영역에는 지뢰가 무조건 있다고 가정해도 된다. 최대화가 목표이기 때문이다. 외곽선과 붙어있는 영역의 지뢰를 최대화하라고 하지만, 사실 지뢰의 개수를 유일하게 결정할 수 있다. 모서리에 있는 지뢰를 제외한 모든 지뢰는 주위 3개의 셀에게 노출된다. 즉 모서리 지뢰를 제거하면 나머지 지뢰의 수는 적혀있는 숫자의 합 / 3 이라는 것이다. 모서리에 있는 지뢰는 모서리에 있는 숫자로 존재 여부를 결정할 수 있으니, 이를 결정하고 나머지 숫자의 합을 세주면 된다. n