프로그래밍28 9020 골드바흐의 추측 https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 8=3+5, 20=17+3 ... 이렇게 소수+소수=짝수를 할 수 있다는게 골드바흐의 추측이다. 반대로 생각하면 짝수에서 어느 소수를 빼면 소수가 나오는 경우가 있다는 말이다. 테스트 케이스에 대해서 소수 판별을 해야하므로 소수 리스트를 미리 구해두는게 더 좋겠다. bool isPrime[10001]; void find(){ for(int i=2; i 2022. 8. 19. 11653 소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net N의 최대 크기가 천만이다. 간단하게 생각해서 N을 2부터 나눠본다. 더이상 2로 나눠지지 않으면 3으로 나눠본다. 더이상 3으로 나눠지지 않으면 4로 나눠본다... 위의 과정을 반복한다. #include int main() { int number, prime = 2; scanf("%d", &number); while (number > 1) { if (number % prime > 0) { prime++; } else { printf("%d\n", prime); number /= prime; } } } 나눗셈에서 나.. 2022. 8. 19. 1018 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 최대 크기가 50x50이다. 그 안에서 각 타일마다 8x8 범위를 스캔한다면 16만 회 정도로 순회하므로 브루트포스 알고리즘을 적용해도 괜찮다. 8x8 범위 내에서 최소 비용으로 칠하려면 체크무늬가 이미 잘 칠해져 있어야 한다. 체크무늬는 흰검흰검... 또는 검흰검흰 순으로 등장하므로 시작할 타일의 색에 따라 값을 스위칭해가며 검사하면 된다. 그러므로 한 칸 씩 이동할 때마다 tile값을 .. 2022. 8. 19. 2293 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 배낭문제의 아류처럼 보이는데, 예전에 했었던 코드들을 살펴봐도 도저히 몰랐다. 지금까지 풀어본 문제중에 비슷했던 것은 N개의 동전들로 K원을 만들 때 최소개수를 구하는 문제였다. 하지만 이 문제는 경우의 수를 구하는 문제여서 매우 헷갈렸다. 10번이나 틀리며 한참 고민한 끝에 상당히 간단한 문제임을 깨달았다. 설명이 난잡하기 때문에 더 좋은 블로그를 소개해야겠다. https://gurumee92.t.. 2022. 8. 17. 11726 2xN 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제를 보자마자 막막했다. 경우의 수가 많을 것 같다는 생각이 들었는데 패턴이 있는지 궁금했다. 일단 작은 길이부터 개수를 계산했다. N = 2) 1x2, 2x1 두 개다. N = 3) 첫 두 개를 돌리거나 뒤에 있는 두 개를 돌리거나 안돌리는 방법까지 총 3개다. N = 4) 다 더해보면 5개다. N = 5) 다 더해보면 8개다. 개수를 세어보니 피보나치 수열과 똑같았다. 설마 답이 그건가 싶어 제출했더니 통과했다... 2022. 8. 16. 2225 합분해 https://www.acmicpc.net/problem/2225 [2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net](https://www.acmicpc.net/problem/2225) 문제가 말하는 대로 합분해를 해보았다. 예를 들어서 0부터 6까지의 정수들 중에 2개를 사용해 6을 만든다고 했을 때 다음과 같은 조합이 나온다. 0 6 1 5 2 4 3 3 4 2 5 1 6 0 여기서 더 나아가 0부터 6까지의 정수들 중에 3개를 사용해 6을 만든다고 했을 때, 다음과 같은 조합을 볼 수 있다. 0 0 6 0 1 5 0 2 4 0 3 3 0 4 2 0 5 1 0 6 0 1 0 5 1 1 4 1 2 3 1 3 2 1 4 1 1 5 0 .. 2022. 8. 14. 이전 1 2 3 4 5 다음
