백준 27172번 - 수 나누기 게임 [C++]

https://www.acmicpc.net/problem/27172솔브드 클래스 5의 골드 4문제. 일단 $N$범위 체크하고 10만인 것을 확인했다. $O(N^2)$ 브루트포스는 당연히 불가.$x$의 최댓값이 100만이었고, 비슷한 문제를 봤었기 때문에 수학 문제 그 중에서도 소수 판정. 에라토스테네스 체 냄새가 강하게 났다.흠... 어떻게 풀어야 하지... 내가 생각한게 맞나? 계속 의심이 들었고 결국 백준 태그를 까봤다.역시 내가 맡은 냄새가 맞았다.내 뇌가 더욱 강하게 에라토스테네스 체를 단순히 사용하는 쪽으로 치우쳤다. [실책]우선 플레이어들의 수를 오름차순으로 정렬한다.정렬된 수를 하나씩 확인하면서 현재 보고있는 수와 나누어 떨어지는 소수 그리고 지금 수를 소수와 나눈 수에 대해 각각 승 패를 ..

알고리즘/백준 · 2025년 01월 02일

백준 17404번 - RGB거리 2 [C++]

https://www.acmicpc.net/problem/17404 솔브드 CLASS 5를 미는 도중 만난 문제.약 두 달 전쯤 수업 시간에 풀다가 아이디어가 안 떠올랐었다.그러다 오늘 다시 도전. [아이디어]RGB거리 문제와 같이 $1$번 집부터 $N - 1$번째 집까지 현재 칠해야 할 집의 바로 앞 집의 색만 신경써서 채워나가고, $N$번 집을 칠할 때만 $N - 1$번 집과 $1$번 집의 색을 고려해주면 된다.근데 여기서 $1$번 집을 고려한다는 것은 $1$번 집에 어떤 색을 칠했었는지 알고 있어야 한다는 의미인데 어떻게 알 수 있을까?$dp[i][j]$ - $1$ ~ $i$번째 집까지 색을 칠하고, $i$번째 집에 색 $j$를 칠할 경우 최소 비용단순하게 RGB거리와 같이 0번 집이 있다고 가정하..

알고리즘/백준 · 2025년 01월 01일