Math

문제 https://leetcode.com/problems/stone-game-ix 풀이 돌을 순서대로 가져가면서, 합이 3의 배수가 되지 않게 해야 하는 게임이다. Alice가 이길 수 있는지 리턴하는 문제이다. 각 돌의 값은 3으로 나눈 나머지만 보면 된다. 합이 3의 배수인지 아닌지만 중요하기 때문이다. 그래서 0, 1, 2의 개수만 세면 충분하다. 0은 합의 나머지를 바꾸지 않으므로, 실제 승부는 1과 2를 어떻게 번갈아 쓰느냐에 달려 있다. count[0]이 짝수인지 홀수인지에 따라 가능한 진행이 달라진다. count[0]이 짝수면 1과 2가 둘 다 있어야 한다. count[0]이 홀수면 1과 2의 개수 차이가 너무 크면 안 된다. 코드 class Solution { func stoneGameIX(_ stones: [Int]) -> Bool { var count = [Int](repeating: 0, count: 3) for stone in stones { count[stone % 3] += 1 } let count0 = count[0] let count1 = count[1] let count2 = count[2] if count0 % 2 == 0 { return count1 > 0 && count2 > 0 } return abs(count1 - count2) > 2 } }

문제 https://leetcode.com/problems/longest-subsequence-with-non-zero-bitwise-xor 풀이 수열 nums가 주어지고, 이 nums의 서브시퀀스 중, 모든 원소를 XOR해서 0이 아니게 되는 서브시퀀스의 최대 길이를 리턴하면 된다. 이 문제는 XOR 연산의 특성을 잘 알아야 한다. 만약 XOR이 아니라 $+$이었다면, 모든 $\text{nums}$의 원소들을 더해보고, 0이 아니라면 $\text{nums}$ 전체를, 0이라면 원소 중 0이 아닌 것 하나를 제외하면 된다. $+$의 역연산은 $-$이므로, 어떤 원소 $x$를 제외했을 때 다음과 같이 된다. $$\sum \text{nums} - x \neq 0$$ 만약 모든 원소가 0이라면 답은 0이 된다. ...

문제 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)