2661번: 좋은수열
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
www.acmicpc.net
좋은 수열이 될 수 있는 과정 나열
1. 최소 값으로 만들기 위해 1, 2, 3 순으로 넣는다.
2. 반복 수열이 발생하면 맨 뒤의 수를 지우고 다음 수를 넣는다.
구상한 전략
- 1, 2, 3을 반복적으로 리스트 배열에 넣고, DFS를 실행하자.
- 이 때, 좋은 수열인지 확인하는 함수를 만들자(check)
특별히 고려한 점
1. check 함수를 만들 때 어떻게 비교를 시켜야하지?
(1) 1 ~ len(res)//2 의 범위를 갖는다.
(2) 빨강의 범위를 슬라이싱 해보자.
- res = [1,2,3,4,5,6]에서 뒤의 3개를 선택하기 위해서는 res[-3], 즉 res[-i]
(3) 파랑의 범위를 슬라이싱 해보자.
- res = [1,2,3,4,5,6]에서 뒤의 빨강 3개와 비교할 파랑 3개를 선택하기 위해서 정할 범위는
- 빨강에서 -i까지 선택했으므로 res[:-i-1]까지 선택할 수 있다.
- 빨강에서 3개를 선택했으므로, 맨 뒤를 기준으로 3*2가 되는 지점을 선택하면 되겠다.
- 결론적으로, 파랑색은 res[-i-i :-i-1]의 범위를 갖는다.
코드
import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/codingtest/venv/input.txt", "rt")
def checker(a):
for i in range(1, len(a)//2 + 1):
if a[-i:] == a[-i-i:-i]:
return False
return True
def DFS(L):
global res
global flag
if flag == 1:
return
if x == L:
flag = 1
for i in res:
print(i, end = '')
return
else:
for i in range(1, 4):
res.append(i)
if checker(res):
DFS(L+1)
res.pop(-1)
if __name__ == '__main__':
flag = 0
res = []
x = int(input())
DFS(0)
'코딩 테스트' 카테고리의 다른 글
[파이썬][백준] 2810번 컵홀더 (0) | 2021.01.07 |
---|---|
[파이썬][백준] 1343번 폴리오미노 (0) | 2021.01.06 |
[파이썬][프로그래머스] 소수 찾기 (0) | 2021.01.04 |
[백준] 14720 우유축제, 파이썬 (0) | 2020.12.24 |
[프로그래머스] 큰 수 만들기 (0) | 2020.12.22 |