[백준] #21313 문어 (python)

21313번: 문어 (acmicpc.net)

21313번: 문어

 

문제

문어에게 여덟개의 팔이 있다는 사실은 잘 알려져 있다. 하지만 문어들이 자신의 팔들을 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의 수열 중 사전순으로 가장 앞서는 것을 출력한다.

이 때, 수열을 이루는 숫자들을 순서대로 공백으로 구분하여 출력한다.

 

예제 입력1

4

예제 출력1

1 2 1 2

 

정말 큣트한 문제군요..

 

---

 

# Code

 

sol1

n = int(input())
ans = [1, 2] * (n//2)
if n%2:
	ans += [3]
print(*ans)

 

sol2

n = int(input())
ans = [1, 2] * (n//2) + ([3] if n%2 else [])
print(*ans)

# Comment

어떻게 하나 생각했는데 생각보다 간단했다.

1. 수열 맨 처음과 맨 끝은 중복될 수 없다.

2. 양 옆의 값은 중복될 수 없다.

3. 사전순으로 가장 앞의 숫자를 사용해야 한다.

n이 짝수일 경우 : 1 2 1 2 ......

n이 홀수일 경우 : 1 2 1 2 ..... 3 

이것도 그리디인가..??? 약간 피곤해서 ㅎ 좀 쉬운거 풀어봤다.. 

 

• ans = [1, 2] * (n//2) + ([3] if n%2 else []) 

이게 의미하는게 [1, 2] 리스트를 n//2 만큼 곱하는건데, 만약에 홀수라면 뒤에 [3] 을 붙인다는 뜻이다. 이런식으로도 표현할 수 있다는 것을 처음 알았다. 파이썬은 .. 신기하다.

• print(*ans) 

이런식으로 for문을 사용하지 않아도 iterator 안의 요소를 모두 출력할 수 있다.