나그네

1963번: 소수 경로 문제 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 4자리 소수 A, B를 입력받고 A를 적절히 바꾸어 B를 만드는데 몇 번 만에 바꿀 수 있는지 구하는 문제다. 바꾸는 데는 규칙이 있다. 1. 한 번에 한 자리 수만 바꿀 수 있다. 2. 바뀐 수도 반드시 소수여야 한다. 소수인지 판단하기 위해 에라토스테네스의 체를 사용해 소수를 걸러준다. 그리고 bfs를 돌렸다. A를 방문처리하고 큐에 넣는다. 이때 큐는 pair를 원소..

1292번: 쉽게 푸는 문제 문제 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 풀이 1 2 2 3 3 3 4 4 4 4 5 와 같이 1을 1번 2를 2번 3을 3번인 수열에서 a번째부터 b번째 수의 합을 구하는 문제다. cnt 변수를 하나 만들어주고 cnt 만큼 cnt를 배열에 추가하도록 했다. 배열 크기가 b를 넘지 않도록 하여 제한을 뒀다. 이후엔 합을 더하면 끝인 간단한 문제다. 코드 #include using namespace std; int main() ..

4839번: 소진법 문제 https://www.acmicpc.net/problem/4839 4839번: 소진법 각 테스트 케이스에 대해서, 입력으로 주어진 수, 공백, 등호, 공백을 출력하고 문제 설명에 나온 것 같이 소진법으로 나타내 출력한다. www.acmicpc.net 풀이 소수의 곱을 이용하는 문제. 다만 수의 범위가 int 범위 안이기 때문에 29까지 곱하게 되면 범위를 벗어나서 23까지의 곱만 구하면 된다. 그래서 누적곱(?) 배열을 만들어줬다. 가장 큰 누적곱부터 비교하며 N이 누적곱보다 같거나 크다면 N을 누적곱으로 나눈 몫과 누적곱까지의 소수 곱을 출력 형식에 맞는 문자열 형태로 만들어 배열에 추가해 줬다. 그리고 N을 누적곱으로 나눈 나머지로 업데이트해 준다. 만약 누적곱 배열을 모두 ..

6500번: 랜덤 숫자 만들기 문제 https://www.acmicpc.net/problem/6500 6500번: 랜덤 숫자 만들기 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, a0을 포함하고 있다. (0 < a0 < 10000) 숫자가 네 자리가 아닌 경우에는, 앞에 0을 추가해 네 자리로 만들어져 있다. www.acmicpc.net 풀이 a0을 입력받고 a0 * a0을 앞에 0을 추가해 8자리 숫자로 바꿔준 다음 가운데 4자리를 a1으로 한다. 이를 반복해 가며 가능한 ai의 수를 구하는 문제. 숫자 N을 입력받고 N*N의 가운데 4자리를 다시 N으로 하며 모든 N을 계속 배열에 넣었다. 그러다 N이 이미 배열 안에 있을 경우 반복문을 탈출한다. 배열의 크기를 출..

26082번: WARBOY 문제 https://www.acmicpc.net/problem/26082 26082번: WARBOY 첫째 줄에 세 양의 정수 $A$, $B$, $C$($1 \le A, B, C \le 1\,000$)가 공백으로 구분되어 주어진다. $\mathbf{\mathit{B}}$는 항상 $\mathbf{\mathit{A}}$의 배수이다. www.acmicpc.net 풀이 경쟁사 제품의 가격 대비 성능을 구한 후 3배한 다음 WARBOY의 가격을 곱한 값을 출력한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int a, b, c; cin >> a >> b >> c; cout

9213번: 꽤 좋은 수 문제 https://www.acmicpc.net/problem/9213 9213번: 꽤 좋은 수 완전수는 자기 자신을 제외한 약수의 합이 자기 자신이 되는 자연수이다. 예를 들어, 6의 약수는 1, 2, 3인데 1+2+3은 6이기 때문에 완전수이고, 28도 1+2+4+7+14 = 28이기 때문에 완전수이다. 어떤 자연 www.acmicpc.net 풀이 자신을 제외한 약수의 합과 자신의 차가 어떠한 수 이하이면 꽤 좋은 수다. 범위 내 꽤 좋은 수의 개수를 구하는 문제. 모든 수에 대해 일일이 약수를 구해 더하면 시간초과가 난다. 그래서 에라토스테네스의 채를 이용해야 한다. i=1부터 100만까지 1씩 증가하며, j=i*2부터 100만까지 i씩 증가하며 j 인덱스의 배열에 i 만큼..

1267번: 핸드폰 요금 문제 https://www.acmicpc.net/problem/1267 1267번: 핸드폰 요금 동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 30초 미만이거나 60초 미만이어도 요금이 나오므로 나눈 후 1을 더하고 요금을 곱하면 된다. 코드 #include using namespace std; int main() { int n, time, y = 0, m = 0; cin >> n; for (int i = 0; i > time; y += 10 * (time / 30 + 1); m..

14622번: 소수 게임 문제 https://www.acmicpc.net/problem/14622 14622번: 소수 게임 인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있 www.acmicpc.net 풀이 에라토스테네스의 체로 미리 500만 이하의 소수를 구해놓은 다음, 입력 범위를 주의하며 차례대로 조건에 따라 구현하면 되는 문제다. 입력받은 수에 따라 조건을 나누어보겠다. 1. 이미 등장한 소수인 경우 이미 등장한 소수인 경우엔 자신이 -1000점을 얻는다. 2. 처음 등장하는 소수인 경우 처음 등장한 소수인 경우엔 해당 소수를 방문처리하고 정렬이 오름차순인 우선순위..

14490번: 백대열 문제 https://www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000) www.acmicpc.net 풀이 N, M을 입력받아 최대한 약분하여 출력하는 문제다. 당연 최대공약수로 나누어주면 그만이다. 입력이 100:10 같은 형태로 입력되기 때문에 cin이 아닌 scanf로 입력을 받았다. 코드 #include using namespace std; // 유클리드 호제법 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int n, m; scanf("%d:%d", &n, &m); int g = gcd(n, m..

27467번: 수학 퀴즈 문제 https://www.acmicpc.net/problem/27467 27467번: 수학 퀴즈 문제에서 설명한 두 실수 $p$, $q$를 출력한다. 단, 정답과의 절대/상대 오차는 $10^{-9}$까지 허용한다. www.acmicpc.net 풀이 복소근에 대한 개념을 알고 있다면 쉽게 풀 수 있는 문제. x^2+x+1=0의 한 복소근 w이므로 w^3 = 1, w^2 = -w-1이다. 따라서 3의 N승일 때, N을 3으로 나눈 나머지로 바꾸어 계산해도 된다. 이후엔 pw + q 의 형태로 계산하여 p와 q를 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL..