문제 https://codeforces.com/problemset/problem/1294/C 풀이 테스트 케이스가 t개 존재한다. 먼저, 정수 n이 주어진다. 각 n에 대해 $n = a \times b \times c, \ a, b, c > 1, \ a \neq b, b \neq c, a \neq c$를 만족하는 세 정수 a, b, c가 존재하면 "YES"와 세 수를 출력하고, 그렇지 않으면 "NO"를 출력하면 된다. 인수 분해 문제이다. n이 3개의 정수의 곱으로 표현되어야 하는데, 3개의 정수가 서로소라는 제약조건은 없다. 64처럼 지수가 6이면 $64 = 2^1 \times 2^2 \times 2^3$ 처럼 표현할 수 있기 때문에 인수와 지수 둘 다 중요하다. ...
문제 https://codeforces.com/problemset/problem/459/B 풀이 n의 원소가 있는 수열 b가 주어진다. b의 원소 두 개를 짝지었을 때, 두 원소의 차이가 가장 클때의 그 차이와, 그 경우의 원소짝의 개수 출력하면 된다. 경우의 수를 구하기 위해 ‘가장 큰 값’을 가진 원소의 개수와 ‘가장 작은 값’을 가진 원소의 개수를 구해야 한다. 가장 큰 값을 가진 원소의 개수를 $maxCount$, 가장 작은 값을 가진 원소의 개수를 $minCount$ 라고 했을 때, 경우의 수는 $maxCount \times minCount$로 어렵지 않게 구할 수 있다. ...
문제 https://codeforces.com/problemset/problem/230/B 풀이 T-Prime을 약수가 3개인 수라고 정의하고, $n$개의 크기의 수열 $x$의 원소 각각에 대해서 그 수가 T-Prime인지 확인하는 문제이다. 약수가 3개라는 뜻은, $1$과 자기 자신 그리고 $\sqrt{x_i}$만을 약수로 가진다는 뜻이다. 즉, T-Prime은 어떤 수의 제곱이어야 한다. 그 ‘어떤 수’의 조건은 무엇일까? 약수의 약수는 결국 약수이다. T-Prime은 $1$, ‘어떤 수’, 자기 자신만을 약수로 가지므로, ‘어떤 수’는 소수여야 한다. 결국 이 문제는 소수 판별 문제로 단순화된다. $x_i$의 최댓값이 $10^{12}$이지만, T-Prime 여부를 판별하려면 $\sqrt{x_i}$가 소수인지만 확인하면 되므로 체는 $\sqrt{10^{12}} = 10^6$까지만 구성하면 충분하다. 에라토스테네스의 체의 시간복잡도는 (거의) $O(N)$이고, 이후 각 쿼리는 $O(1)$에 처리되므로, $n \leq 10^5$인 입력 전체에 대해 전처리 $O(10^6)$ + 쿼리 $O(n)$으로 풀 수 있다. ...
문제 https://codeforces.com/problemset/problem/1/A 풀이 Codeforces에서 푼 첫 문제. $n \times m$ 크기의 직사각형 도시가 있고, 그 도시를 $a \times a$ 크기의 타일로 뒤덮는 문제이다. 타일은 도시 경계를 넘어가도 되지만, 잘라선 안되고 겹쳐도 안된다. 즉, 필요한 타일의 개수는 가로/세로 각각을 $a$로 나눈 값을 올림하여 곱하면 된다. 문제에 간단한 함정이 하나 있는데, n, m, a의 범위가 최대 $10^9$이라 곱셈 결과가 int 범위를 넘어갈 수 있으므로 long long을 사용을 사용해야 한다. 코드 #include <iostream> #include <cmath> int main() { long long n, m, a; std::cin >> n >> m >> a; std::cout << ((n + a - 1) / a) * ((m + a - 1) / a) << std::endl; return 0; }
문제 https://school.programmers.co.kr/learn/courses/30/lessons/12987 풀이 n의 값이 최대 10000, s의 값이 최대 1000000의 값을 가질 수 있으므로 모든 경우의 수를 DFS로 탐색하는 것은 매우 비효율적이다. 하지만 수학적 직관을 이용해 생각해보자. 예시로 주어진 s = 9, n = 2인 경우에서도 {4, 5}가 최고의 집합이다. 만약 s = 5, n = 2인 경우에는? {2, 3}이다. s = 10, n = 2인 경우는 {5, 5} 이다. 집합 원소들이 최대한 고르게 되어있을 때 원소들의 곱이 최대가 된다는 것(= 최고의 집합이라는 것)을 알 수 있다. 그러면 이 직관을 증명해보자. ...
문제 https://www.acmicpc.net/problem/17266 풀이 가로등 간의 최대 간격을 찾으면 되는 문제이다. 일반적인 가로등 간의 간격과, 시작점과 첫 가로등의 간격, 도착점과 마지막 가로등의 간격을 알아내면 된다. 가로등 사이의 간격은 양 사이드 모두가 가로등이기 때문에 간격에서 2를 나눠줄 필요가 있다. 이 문제에는 작은 함정이 하나 있는데, 가로등 사이의 간격이 만약 홀수인 경우에는 2로 나눴을 때 0.5가 내림 되기 때문에 주의해야 한다. 코드 import Foundation let n = Int(readLine()!)! let m = Int(readLine()!)! let x = readLine()!.split(separator: " ").map { Int($0)! } var answer = max(x.first!, n - x.last!) for idx in 1..<m { let interval = Int(ceil(Double(x[idx] - x[idx - 1]) / 2.0)) if interval > answer { answer = interval } } print(answer)