[그리디 알고리즘 Lv.04] 21313번 문어 (규칙 찾기)

1. 문제

    문어 다리 엮기 문제 (링크 참고)

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

21313번: 문어

 

2. 문제 포인트

• 문어의 수(N)는 N(4 ≤ N ≤ 1,000)이다
• 문어 다리의 번호는 중복이 없다
  • = 같은 숫자가 두번 이상 나오면 안된다

• 사전상 가장 앞에오는 수열을 찾는다
  • = 최대한 1과 2를 사용해야 한다

 

 

반응형

 

 

3. 접근법

• 문어 다리를 엮는 패턴 인식하기

• 문어의 숫자가 짝수인 경우 (N % 2 == 0)
  • 1과 2가 문어의 숫자만큼 반복되면 첫번째 숫자를 찾을 수 있음
• 문어의 숫자가 홀수인 경우 (N % 2 == 1)
  • 1과 2가 반복하되 마지막 문어는 3번 다리로 1번 문어와 손을 잡아야 한다
  • 사전상 가장 앞 수열은 1과 2를 이용해야 하나 위의 그림에서 5번 문어는 1번과 1번손을 잡을 수 없고(1번문어의 1번손은 2번과 잡음) 2번 손은 4번 문어가 3번과 이미 잡았기에 사용 할 수 없다. 따라서 5번 문어는 3번을 사용해야 한다

4. 결과 코드

import sys

# 문어 수 입력 받기
n = int(sys.stdin.readline().strip())

if n % 2 == 0:  #문어가 짝수인 경우
    # 문어 숫자 만큼 1과 2 반복
    result = [1, 2] * (n//2)
        print(*result)
    
else:  #문어가 홀수인 경우
	# n - 1번째까지 1,2반복
    result = [1,2] * (n//2)
    
    # 마지막 n번째에 3을 추가
    result.append(3)
    print(*result)

print(a)