CSES - Weird Algorithm
문제 정보
| 항목 | 내용 |
|---|---|
| 시간 제한 | 1.00s |
| 메모리 제한 | 512MB |
| 제출 일자 | 2026-04-20 |
| 소요 시간 | 0.06s |
문제 설명
Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:
\[3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\]Your task is to simulate the execution of the algorithm for a given value of n.
Input
The only input line contains an integer n.
Output
Print a line that contains all values of n during the algorithm.
Constraints
\[1 \le n \le 10^6\]Example
Input:
1
3
Output:
1
3 10 5 16 8 4 2 1
🇰🇷 한국어 번역 (클릭하여 펼치기)
양의 정수 $n$을 입력으로 받는 알고리즘을 생각해 봅시다.
- $n$이 짝수라면, 알고리즘은 이를 2로 나눕니다.
- $n$이 홀수라면, 알고리즘은 $n$에 3을 곱하고 1을 더합니다.
알고리즘은 $n$이 1이 될 때까지 이 과정을 반복합니다. 예를 들어, $n=3$일 때의 수열은 다음과 같습니다: \(3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\)
당신의 임무는 주어진 $n$에 대해 이 알고리즘의 실행 과정을 시뮬레이션하는 것입니다.
입력
첫 번째 줄에 정수 $n$이 주어집니다.
출력
알고리즘이 진행되는 동안의 모든 $n$의 값을 한 줄에 공백으로 구분하여 출력합니다.
제한 사항
- $1 \le n \le 10^6$
예제
입력:
1
3
출력:
1
3 10 5 16 8 4 2 1
- 2026 05 04 수정.
초기 접근 및 로직 구상 방식
- n이 짝수면 2로 나누고, 홀수이면 n * 3 + 1 해줌. n이 1이 될때까지 반복.
- 짝수면 n % 2 == 0이고, 홀수면 n % 2 != 0. if문 사용으로 n이 1까지, while문으로 n이 1까지 돌리는게 제일 간단해보임.
시도
1차 시도는 .
-실패, 처음 n 출력을 못보고 출력하지 않아 틀림.
1차 시도 코드 (클릭하여 펼치기)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class WeirdAlgorithm {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
sb.append(n).append(" ");
} else {
n = n * 3 + 1;
sb.append(n).append(" ");
}
}
System.out.println(sb); // 맨 처음 n 값을 생략하고 바로 연산한 값이 출력됨
}
}
2차 시도는 .
-실패. 정수값에서 오버플로우가 발생했다. 아마 int로도 충분하지 못한거 같다.
2차 시도 코드 (클릭하여 펼치기)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class WeirdAlgorithm {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); // 오버 플로우 발생.
StringBuilder sb = new StringBuilder();
sb.append(n).append(" "); // 출력시 처음 n값을 출력하기 위해 추가.
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
sb.append(n).append(" ");
} else {
n = n * 3 + 1;
sb.append(n).append(" ");
}
}
System.out.println(sb);
}
}
3차 시도는 . -성공. int를 long으로 바꾸니 성공했다.
배운 점
- 데이터 크기에 따라서 int, long등을 선언 할 줄 알아야함. 특히나 n의 범위가 int값 안에 들어간다 하더라도, 연산이 들어가면 이야기가 달라짐.
최종 풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class WeirdAlgorithm {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
sb.append(n).append(" ");
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
} else {
n = n * 3 + 1;
}
sb.append(n).append(" ");
}
System.out.println(sb);
}
}