나그네

27959번: 초코바 문제 https://www.acmicpc.net/problem/27959 27959번: 초코바 밤고는 $100$원 동전을 $N$개 갖고 있고, 그 돈으로 가격이 $M$원인 초코바를 사 먹으려고 한다. 밤고는 갖고 있는 돈으로 초코바를 사 먹을 수 있는지 알고 싶어 한다. 밤고가 가진 돈이 초코바의 www.acmicpc.net 풀이 100원 동전 N개로는 100 * N원 이하의 초코바만 살 수 있으므로 100 * N ≥ M인 경우 초코바를 살 수 있다. 이 경우 Yes를 출력하고 이외의 경우 No를 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin..

27880번: Gahui and Soongsil University station 문제 https://www.acmicpc.net/problem/27880 27880번: Gahui and Soongsil University station Soongsil University Station is famous as the deepest station on Seoul Subway Line 7. This station is so deep that the platform is on the B6. Gahui was surprised that she did not reach the platform after more than five minutes from the exit. Gahui wants to www.acmic..

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의 모든 약수의 합을 값으로 가..

27724번: 팝핀 소다 문제 https://www.acmicpc.net/problem/27724 27724번: 팝핀 소다 입력의 첫 번째 줄에 대회에 참가하는 선수의 수 $N$, 일어날 수 있는 이변의 수 $M$, 시은이의 탄산 내성 $K$가 공백으로 구분되어 주어진다. 주어지는 모든 수는 정수이다. $(2 \le N \le 262\,144;$ $0 \le www.acmicpc.net 풀이 대회가 토너먼트 형식이므로 항상 자신이 이길 수 있는 상대와 대결해야 최대한으로 승리할 수 있다. 따라서 시은이의 탄산 내성이 K일 때, 시은이가 이길 수 있는 최대 대결의 수는 log2 K번이다. 만약 이변이 있는 경우, 최대한 이길 수 있는 다음 이변의 수만큼 더 이길 수 있다. 따라서 최대 log2 K + M번..

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승이 범위 내인지 확인하려면 (..

12020번: LU 분해 문제 https://www.acmicpc.net/problem/12020 12020번: LU 분해 \(N \times N\) Matrix A가 주어진다. LU 분해란 \(A = LU\)꼴의 Matrix 곱로 분해하는 것이다. (단, \(L\)은 Lower Triangular Matrix, \(U\)는 Upper Triangular Matrix) Lower Triangular Matrix란 \(L_{ij} = 0 \text{ (if }i < j\text{)}\) Upper www.acmicpc.net 풀이 선형대수학에서 배우는 LU 분해를 구현하는 문제다. 구현 자체는 LU 분해를 하는 방식대로 하면 된다. LU 분해에 대해선 설명 잘해놓은 다른 블로그를 참고하는 게 좋을 것 같다..

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)이다. 코드 #..

27512번: 스네이크 문제 https://www.acmicpc.net/problem/27512 27512번: 스네이크 두 정수 $n$과 $m$이 한 줄에 공백으로 분리되어 주어집니다. ($2 \le n,m \le 200$) www.acmicpc.net 풀이 N × M 격자에서 뱀의 머리와 꼬리가 맞닿아 있으면서 길이가 가장 긴 것을 구하는 문제다. 처음엔 사각형 외곽을 두르는 길이라고 생각했으나 사실 꼬불꼬불하게 가면 더 길어질 수 있다. 그리고 규칙이 있는데 N과 M 중 하나라도 짝수면 뱀은 N × M 격자를 모두 지날 수 있다. 둘 중 하나라도 짝수가 아니라면 즉, 둘 다 홀수라면 뱀은 아무리 꼬불꼬불하게 가더라도 한 칸은 지나갈 수 없다. 코드 #include using namespace std;..

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..