문어
1 초 | 1024 MB | 1673 | 1129 | 983 | 66.780% |
문제
문어에게 여덟개의 팔이 있다는 사실은 잘 알려져 있다. 하지만 문어들이 자신의 팔들을 1번, 2번, 3번, ..., 8번이라고 부른다는 말은 오늘 처음 들었을 것이다! 단, 시계방향으로 오름차순이라던가 하는 규칙은 없다. (물론 그러한 문어도 존재할 수 있다.) 문제에선 편의상 팔 대신 손이라고 부르자.
문어들은 정월 대보름을 맞아 강강술래를 하려고 한다. 각 문어는 양 옆의 서로 다른 두 문어와 손을 맞잡아 원을 만든다. 문어끼리 손을 잡을 때 지켜야 할 예절이 있다.
- 서로 같은 번호의 손을 잡아야 한다.
- 한 문어와 둘 이상의 손을 잡을 수 없다.
- 한 손으로 여러 문어의 손을 잡을 수 없다.
모든 문어들은 예의바르기 때문에 예절을 항상 따른다.
강강술래를 하는 N마리의 문어 중 하나를 골라 1번 문어라 하자. 1번 문어를 기준으로 시계방향 순으로 2번, 3번, 4번, ..., N번 문어라고 부르자. 우리는 인접한 두 문어가 잡은 손의 번호를 이용하여 길이 N의 수열을 만들 것이다. 1번과 2번 문어가 잡은 손의 번호는 1번째 항, 2번과 3번 문어가 잡은 손의 번호는 2번째 항, ..., N - 1번과 N번 문어가 잡은 손의 번호는 N - 1번째 항, N번 문어와 1번 문어가 잡은 손의 번호는 N번째 항이다.
문어의 수 N이 주어질 때, 이렇게 만들 수 있는 수열 중 사전순으로 제일 앞서는 수열을 알아보자. 다음은 문어가 4마리일 때 사전순으로 제일 앞서는 수열인 1 2 1 2 를 만드는 방법이다.
입력
문어의 수 N(4 ≤ N ≤ 1,000)이 주어진다.
출력
N마리의 문어들로 만들 수 있는 길이 N의 수열 중 사전순으로 가장 앞서는 것을 출력한다.
이 때, 수열을 이루는 숫자들을 순서대로 공백으로 구분하여 출력한다.
예제 입력
4
예제 출력
1 2 1 2
힌트
길이가 같은 두 수열에 대해, 작은 번호부터 시작해 같은 번호의 항끼리 비교하여 더 작은 수가 먼저 나오는 수열이 사전순으로 앞선다.
예를 들어 두 수열 A = {7, 3, 5} 와 B = {7, 4, 1} 가 있다고 하자. A1과 B1은 7로 서로 같다. A2와 B2는 각각 3과 4로 다르며, A2가 더 작으므로 수열 A는 수열 B보다 사전순으로 앞선다.
코드
package 문어;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
[시간 복잡도] -> O(N)
- "1 2" 패턴을 반복하여 배열을 채움
[핵심 개념]
1. 사전순: 가능한 가장 작은 숫자인 1과 2를 번갈아 사용하여 수열을 생성합니다.
2. 짝수와 홀수 처리: 짝수 문어의 경우 "1 2" 패턴을 반복하고, 홀수 문어의 경우 마지막에 3을 추가합니다.
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int numOcto = Integer.parseInt(reader.readLine());
reader.close();
// 결과를 저장할 배열
int[] handArr = new int[numOcto];
/*
문어의 수가 짝수일 경우
[사용 이융]
- `numOcto / 2` : `1 2` 패턴을 반복적으로 배열에 채우기 위해 몇 번 반복해야 하는지를 결정합니다.
짝수와 홀수에 대해 패턴을 생성하는 중요한 역할을합니다.
*/
for (int i = 0; i < numOcto / 2; i++) {
handArr[2 * i] = 1;
handArr[2 * i + 1] = 2;
}
// 문어의 수가 홀수일 경우 마지막 요소 처리
if (numOcto % 2 != 0) handArr[numOcto - 1] = 3;
// 결과 출력
for (int hand : handArr) System.out.print(hand + " ");
}
}
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 쉽게푸는문제 - 1292번 (0) | 2024.06.17 |
---|---|
[백준] 적어도 대부분의 배수 - 1145번 (1) | 2024.06.17 |
[백준] 가장긴감소하는부분수열 - 11722번 (0) | 2024.06.15 |
[백준] 부녀회장이될테야 - 2775번 (1) | 2024.06.15 |
[백준] 핸드폰 번호 궁합 - 17202번호 (1) | 2024.06.15 |