나그네

14715번: 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) 문제 https://www.acmicpc.net/problem/14715 14715번: 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) 첫 번째 줄에 처음 주어진 슬라임의 에너지 K (2 ≤ K ≤ 1, 000, 000) 가 주어진다. www.acmicpc.net 풀이 간단한 정수론 문제입니다. K = A × B 형태로만 분할할 수 있으므로 최종적인 형태는 소인수분해된 형태임을 예측할 수 있습니다. 즉, K가 100일 때, 100 = 2^2 × 5^2 이므로 4개의 소인수로 분해됩니다. 이 문제는 흠집이 제일 많이 생긴 슬라임의 흠집 개수의 최소를 구하는 문제입니다. 흠집을 최소화하기 위해선 가능한한 완전 이진 트리 형태로 분할하는..

29158번: 큰 수 만들기 게임 문제 https://www.acmicpc.net/problem/29158 29158번: 큰 수 만들기 게임 성현이와 지훈이는 큰 수 만들기 게임을 하고 있다. 성현이는 양의 정수 $N$이 적힌 카드 $1$장이 들어 있는 주머니를 들고 있다. 지훈이는 성현이의 카드를 몰래 본 다음 성현이의 카드에 적힌 $N$ www.acmicpc.net 풀이 큰 수를 만드는 테크닉은 16496 - 큰 수 만들기 문제와 동일하다. 각각의 수를 문자열로 a = "1", b = "2"인 경우 ab = "12" ba = "21"로 더 큰 수를 만들 수 있는 것은 ba다. 이 정렬 조건으로 수를 정렬한 다음 차례대로 나열하면 된다. 먼저 동작 1과 동작 2가 있는데, 동작 1은 2 이상의 K로 2..

29159번: 케이크 두 개 문제 https://www.acmicpc.net/problem/29159 29159번: 케이크 두 개 $(0,0),(0,1),(1,0),(1,1)$이 네 쪽지점인 직사각형과 $(2,1),(3,2),(3,1),(3,2)$가 네 꼭지점인 직사각형을 동시에 이등분하는 직선의 방정식은 $y=\frac12 x+\frac14$이다. www.acmicpc.net 풀이 두 직사각형 각각의 중심 좌표를 구하고, 두 점을 지나는 일차방정식을 구하는 문제다. 분수 형태의 출력 형식 때문에 애를 먹은 문제다. 먼저 일차방정식의 형태를 보면 y - y1 = ((x2 - x1)/(y2 - y1))(x - x1)이다. y = Px + Q 형태로 나타냈을 때 P와 Q를 출력하는 문제다. 먼저 기울기 P ..

28683번: 피타! 피타! 피타츄! 문제 https://www.acmicpc.net/problem/28683 28683번: 피타! 피타! 피타츄! 포켓몬스터를 좋아하는 종우는 포켓몬스터를 연구하다가 포켓몬스터가 상당히 수학적이고 코딩과 밀접한 관련이 있는 게임이라는 것을 알게 되었다. 모든 이동은 유클리드 공간에 평행하게 이 www.acmicpc.net 풀이 대회 당시에는 문제를 해결하지 못했다. 친구의 설명으로 문제를 해결하고 에디토리얼을 참고했다. 몇 가지 조건을 나누어 문제를 해결할 수 있다. 1. n이 제곱수인 경우 √n은 정수다. 임의의 정수 a에 대해 (√n, a, √(n+a^2))이 직각삼각형을 이루고, 두 변의 길이가 √n과 a로 정수이므로 무한하다. 2. n이 제곱수가 아닌 경우 나머지..

27965번: N결수 문제 https://www.acmicpc.net/problem/27965 27965번: N결수 $10$진법 상에서 양의 정수 $1$, $2$, $3$, $\cdots$, $N$을 이어 붙여 만든 수 $\overline{123\cdots N}$을 $N$결수라고 한다. 예를 들어 $12345$는 $5$결수이고, $12345678910111213$은 $13$결수이다. $N$과 정수 $K$가 주어 www.acmicpc.net 풀이 N결수를 만들고 K로 나누기엔 N결수가 너무 큰 수가 되기 때문에 long long의 범위를 벗어나게 된다. 따라서 과정을 쪼개 중간중간에 나머지 연산을 해야한다. N = 5, K = 7인 경우를 예로 들면, 1~5를 차례대로 나열해야한다. 이때 1을 K로 나눈 ..

17425번: 약수의 합 문제 https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 풀이 예전에 모든 수의 약수의 합을 에라토스테네스의 체를 사용해 구하는 법을 9213번 문제를 통해 만들어봤다. [9213 꽤 좋은 수 해설] 링크를 참고해 주길. 어떤 수 A은 A의 배수의 약수다. 범위 내 모든 A의 배수에 A을 더해준다. 그러면 sieve의 A번 인덱스에는 A의 모든 약수의 합을 값으로 가..

14941번: 호기심 문제 https://www.acmicpc.net/problem/14941 14941번: 호기심 첫 줄에는 질문의 개수 n이 주어진다. 다음 줄 부터 차례대로 함수의 입력 a, b가 주어진다. (1 ≤ a ≤ b ≤ 105) 또한 남규는 호기심이 많기 때문에 매우 많은 질문을 한다. 따라서 질문의 수 n은 최 www.acmicpc.net 풀이 a 이상 b 이하의 소수를 규칙에 따라 계산하는 간단한 문제다. 먼저 에라토스테네스의 체를 사용해 10^5보다 작은 소수를 걸러낸다. 소수를 하나하나 a보다 큰지 비교하다는 방법은 시간복잡도가 O(N)이고 10^5 이하의 소수는 약 41,000개 이상이고 테스트케이스의 수 N이 10^5이기 때문에 시간초과가 난다. 따라서 prime 배열은 이미 ..

1456번: 거의 소수 문제 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 풀이 거의 소수는 소수의 N제곱 형태인 수를 말한다. 범위 내 거의 소수의 개수를 구하는 문제다. 수의 범위가 10^14이고 N제곱 형태를 구하므로 에라토스테네스의 체를 사용해 10^7까지의 소수만 구해준다. 소수를 i라고 한다면 i^2 = i × i부터 범위에 포함된다면 카운트를 증가시켜 주면 된다. 단, 범위 판단에 주의해야한다. 현재 수의 +1승이 범위 내인지 확인하려면 (..

1188번: 음식 평론가 문제 https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 풀이 소시지의 개수 N과 평론가의 수 M을 입력받고 소시지 N개를 모두 균등하게 나누어 평론가 M명에게 같은 양을 나누어 준다. 이때 소시지를 자르는 횟수를 구하는 문제다. 소시지를 일자로 세우고 M등분하면 된다. 이때 칼질의 횟수는 M-1번이 된다. 그러나 이미 소시지는 N개를 일자로 나열한 것이므로 N등분되어있다. 따라서 중복으로 잘리는 횟수를 구해 빼주면 된다. 중복인 칼질의 수는 (N과 M의 최대공약수) - 1 이므로 정답은 M - gcd(N, M)이다. 코드 #..

1016번: 제곱 ㄴㄴ 수 문제 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 풀이 min 이상 max 이하의 제곱 ㄴㄴ 수의 개수를 구하는 문제다. 제곱 ㄴㄴ 수란 어느 제곱수로 나누어 떨어지지 않는 수를 말한다. 이 문제의 핵심은 에라토스테네스의 체의 변형이다. 1 ≤ min ≤ 1,000,000,000,000 min ≤ max ≤ min + 1,000,000 위와 같은 범위 때문에 애를 먹었다. 아래 범위 조건 때문에 0..