[Coding Test] Programmers_Summer&Winter Coding(2019) 종이접기

이런 부분은 이렇게 사용했으면 좋겠다! 싶거나 추가했으면 하는 내용은 과감히 댓글 부탁드립니다.

 

[SUMMER&WINTER CODING 종이접기]

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다.

먼저 오른쪽 절반을 왼쪽으로 접습니다.

다시 오른쪽 절반을 왼쪽으로 접습니다.

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다.

 

위 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

 

종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 종이를 접는 횟수 n은 1 이상 20 이하의 자연수입니다.

• 종이를 접었다 편 후 생긴 굴곡이 ∨ 모양이면 0, ∧ 모양이면 1로 나타냅니다.

• 가장 왼쪽의 굴곡 모양부터 순서대로 배열에 담아 return 해주세요.

 

입출력 예

Input:

1
2
3

output:

[0]
[0,0,1]
[0,0,1,0,0,1,1]

 

입출력 예 설명

입출력 예 #1
종이의 오른쪽 절반을 왼쪽으로 한번 접었다 펴면 아래 그림과 같이 굴곡이 생깁니다.

따라서 [0]을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같습니다.

입출력 예 #3
종이를 절반씩 세 번 접은 후 다시 펼치면 아래 그림과 같이 굴곡이 생깁니다.

따라서 [0,0,1,0,0,1,1]을 return 하면 됩니다.

 

---

잠시 산책하기 전에 해당 문제를 보고 나갔습니다.

종이를 접고 펼쳤을 때 위로 튀어나오는 부분의 개수라.. 전혀 생각지도 못 했던 패턴이었어요.

궁금한 마음에 주머니에 있던 지폐를 접어가며 답을 찾아갔습니다.

 

일단 결과로 나와야 할 내용은 접힌 종이를 펼쳤을 때 위/아래로 접힌 부분인 것이죠.

해당 결과를 계산해내기 전에 총 자국 수를 생각해보았어요.

 

위 예시에서는 3번까지만 접기에 제가 직접 지폐로 4번 접어봤어요.

1번 접었을 때부터 4번 접었을 때의 총 자국 수는 각 1, 3, 7, 15개 입니다.

2 - 4 - 8 순서로 늘어나는군요.

접은 횟수가 n > 1일 때, 증가 수는 2^(n-1)입니다. +1을 하면 총 자국수가 되어 식으로 보기 좋게 표현했어요.

{2^(n-1)} + 1

 

생각해보니 해결하는 문제에선 필요하지 않은 내용이네요.

 

다시 돌아와서,

n = 1  [0]
n = 2  [0,0,1]
n = 3  [0,0,1,0,0,1,1]
n = 4  [0,0,1,0,0,1,1,0,0,0,1,1,0,1,1]

n = 3이면 n=2에서 [0,0,1,1]이 추가되고, n = 4이면 n=3에서 [0,0,0,1,1,0,1,1]이 추가됩니다.

여기에서 우리는 패턴을 찾을 수 있습니다. 사실 n=3 까지는 감이 아예 안왔는데 4부터는 조금이나마 눈을 뜬 신생아 같았죠.

 

n이 4일 때로 가정해볼게요.

for문을 이용했을 때, 첫 번째 패턴에서는 answer = [0, 0, 1], 두 번째 패턴에서는 answer = answer + [0, 0, 1, 1], 마지막 패턴에서 answer = answer + [0,0,0,1,1,0,1,1]을 각각 추가해주면 됩니다.

answer 뒤에 더해질 값을 어떻게 구하느냐가 문제였고 해결을 위해 다른 분들의 코드를 참고하며 많은 시간을 소요했죠. 결과적으로 아래와 같은 계산이 필요했습니다.

answer = answer + [0] + [answer 자리수에 맞춰 0과 1로 계속 바뀌는 수]

 

 

XOR연산을 통한 센스있는 접근법이 눈에 띄었고 그 것을 참고하여 작성한 코드에요!(언젠간 나도....)

def solution(n):
    answer = [0]

    for i in range(n - 1):
        answer = answer + [0] + [sw ^ 1 for sw in answer[::-1]]

    return answer

 

 

 

HyunJin-Jeong/Practice_CodingTest-Python