[백준] 21313 문어 - 파이썬(Python)

문제 - 21313

https://www.acmicpc.net/problem/21313

문제에서 핵심만 뽑자면 다음과 같다.

• 문어의 팔은 1~8 숫자로 부르는데, 규칙은 없다.

• 서로 같은 번호 손을 잡는다.

• 한 문어와 둘 이상 손을 잡을 수 없다.

• 한 손으로 여러 문어의 손을 잡을 수 없다.

• 1번과 2번 문어가 잡은 손의 번호는 1번째 항, 2번과 3번 문어가 잡은 손의 번호는 2번째 항, ..., N - 1번과 N번 문어가 잡은 손의 번호는 N - 1번째 항, N번 문어와 1번 문어가 잡은 손의 번호는 N번째 항이다.

• 문어의 수 N이 주어질 때, 이렇게 만들 수 있는 수열 중 사전순으로 제일 앞서는 수열을 알아보자

해결 방법

문제 그대로 해결하기

문제 그대로 읽고 해결 방법을 생각하면 다음과 같다.

1. 1번과 2번 문어가 손 1을 잡으면 2번 문어는 3번 문어와 손 1을 잡을 수 없다.
2. 즉, 2번 문어는 1을 제외한 2~8까지 손으로 다음 문어와 손을 잡아야한다.
3. 그 중 사전 순으로 제일 앞서야 하는 조건으로 인해 그중 가장 작은 숫자 손을 잡는다.

문어들이 손을 잡는 수열 중 사전 순으로 제일 앞서는 기준에 따라. 이전 문어와 잡지 않은 손 중 가장 작은 숫자의 손으로 다음 문어와 손을 잡아야한다. 단, 마지막 문어는 N-1문어가 잡지 않은 손 중 가장 작은 숫자의 손 이외에도, 1번 문어와 손을 잡기 때문에 1번 문어가 잡지 않은 손 역시 고려해야한다.
사전 순을 고려하면 1번 문어는 반드시 1번 손을 사용해야한다.

import sys

N = int(sys.stdin.readline())
answer = [1]

for i in range(1, N):
  if i == N-1:
    next =  min([n for n in range(1,9) if answer[i-1] != n and answer[0] != n])
  else:
    next = min([n for n in range(1,9) if answer[i-1] != n])
  answer.append(next)

print(*answer)

그러나 이와 같이 풀이하면 N 회 반복마다 6-7회 반복, min 으로 인해 6-7회 반복

총합 N * (다리 개수 - 1 or 2)^2 으로 대략 O(N*M^2) 의 시간이 걸린다.
해당 문제의 경우 N의 최대가 1,000 이기 때문에 1초라는 제한에 걸리지 않는다.

규칙을 찾아 해결하기

사실 문제 조건에 따라 나열하면
문어 4마리 경우 - 1 2 1 2
문어 5마리 경우 - 1 2 1 2 3

문어 6마리 경우 - 1 2 1 2 1 2
문어 7마리 경우 - 1 2 1 2 1 2 3

결과적으로 긴 풀이를 수열의 조건으로 나열하면

1. 사전순으로 나열하기 위해 가장 작은 숫자를 사용
2. 수열의 양 옆 값은 중복일 수 없음
3. 수열의 양 끝 값이 중복일 수 없음.

즉 N 이 짝수면 1 2 1 2 ....
N 이 홀수면 맨 뒤만 3이 붙는다.

import sys

N = int(sys.stdin.readline())
print(*[1, 2] * (N//2) + ([3] if N % 2 == 1 else []))