kth990303의 코딩 블로그

PS 단톡방에서 추천받은 문제. (이거 왜 골드2..? 꽤나 어려웠다.) 문제는 아래와 같다. https://www.acmicpc.net/problem/14578 14578번: 영훈이의 색칠공부 영훈이가 색칠 할 수 있는 모든 경우의 수를 1,000,000,007로 나눈 나머지를 출력하시오. www.acmicpc.net 의식의 흐름 및 해설 처음에는 b, r을 놓을 수 있는 경우의 수 nC2로 접근하는데 방법이 잘 생각나지 않았다. 2*2부터 순서대로 도형을 그리면 생각나는 dp식이 있지 않을까 접근해보았는데, 오히려 2*2에서 가능했던 경우의 수가 3*3으로 확장되는 경우가 한 가지도 없었다. (눈치빠른 사람이라면 여기서 무언가 눈치챘을 수도 있다.) 좀 더 고민해보다가, 색이 어차피 두 가지뿐이므로 ..

학교 채점현황을 둘러보다가 발견한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 의식의 흐름 및 해설 소수 문제인데 팰린드롬이어야 하는 문제이다. 범위가 1억까지이기 때문에 애매하게 시간초과가 될까말까한 문제처럼 보였는데, 생각해보니 팰린드롬인지 체크해주는 과정 때문에 O(1억 * s.length())이므로 시간초과가 나오기 충분한 시간복잡도였다. 특히, 수가 클수록 수가 많으므로 (ex.10 ~100..

문제 https://www.acmicpc.net/problem/15897 15897번: 잘못 구현한 에라토스테네스의 체 성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너 www.acmicpc.net 꽤 어렵게 다가온 수학문제이다. N이 1e9이므로 O(N)은 시간초과가 발생한다. 어떻게 해결해야 할까? Harmonic Lemma (조화수열의 성질) 예시로 N=6인 경우를 들어보자. j의 값은 i의 값이 더해지므로, i의 값이 횟수에 영향을 준다. 맨 처음에 j는 디폴트값으로 1이므로, 1+(N-1)/i의 값이 횟수가 됨을 확인할 수 있다. 그러나, 아직까지는 아래 O(N) ..