초등부 올림피아드 2003 전국본선 3번문제
요즘 초등학교 문제밖에 안푸는거 같네요..ㅡㅜ(그것도 과외시간에 풀게 되네요.ㅎㅎ)
이문제가 상당히 괜찮은 문제인거 같습니다. 그렇게 어렵지도 않구요. https://www.kado.or.kr/koi/F04000000000/F04040000000Q.asp?intExBaSEQ=31&strExBaPart=20&strExBaGrad=01&strExBaYear=2003&ExPmSEQ=355
ps1. 그리고 이사이트의 고급 알고리즘 동영상도 꽤 괜찮은거 같네요.(특히 백트랙킹과 계산기하는 추천합니다. 다른건 안봐서..ㅡㅠ)
ps2. 그리고 아래의 글은 문제를 풀어보셨거나, 안풀 사람만 보시길 바랍니다.
처음에는 O(n^2)에 풀릴줄 알았는데, 몇가지 트릭(?)을 쓰면 O(n)에 풀리는 군요. 이때까지 다이나믹에 대해서 많이 알고 있다고 생각했는데, 기초적인 부분이나 대충 공부했던 부분이 많은거 같습니다.
