[프로그래머스-Level 03] 종이접기(c++)

문제 설명

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

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

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

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

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

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

제한사항

• 종이를 접는 횟수 n은 1 이상 20 이하의 자연수입니다.
• 종이를 접었다 편 후 생긴 굴곡이 ∨ 모양이면 0, ∧ 모양이면 1로 나타냅니다.
• 가장 왼쪽의 굴곡 모양부터 순서대로 배열에 담아 return 해주세요.

---

입출력 예

nresult

1	[0]
2	[0,0,1]
3	[0,0,1,0,0,1,1]

입출력 예 설명

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

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

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

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

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

 

---

내 풀이

 

처음에는 좀 당황했지만 생각보다 쉬운문제였다.

 

아래와 같은 입출력 예를 보았을때,

1	[0]
2	[0,0,1]
3	[0,0,1,0,0,1,1]

 

출력값의 사이즈는 항상 홀수이고 가운데(접히는 부분) 값은 항상 0이다.

 

n=4 일때, 

 

위의 그림과 같은 출력값이 나온다. 중괄호로 묶인 것을 뭉텅이라고 했을 때,

왼쪽 뭉텅이를 보면 n=3 출력값과 완전히 똑같고 오른쪽 뭉텅이를 보면 가운데 값이 1로 바뀐 것 빼고는 똑같은 것을 알 수 있다. 

 

그렇기 때문에 n에 대해서 항상 n-1 인 출력값에 + 0 + (가운데값을 1로 고친 n-1 출력값) 이렇게 넣어주면 된다!

 

전체 소스코드 

#include <iostream>
#include <vector>
using namespace std;

vector<int> paper;

void nFold(int num) {

	/* 1번접기 2번접기 초기화 */
	if (num == 1)
		paper.push_back(0);
	else if (num == 2) {
		paper.push_back(0);
		paper.push_back(0);
		paper.push_back(1);
	}
	else {
		paper.push_back(0);
		paper.push_back(0);
		paper.push_back(1);

		/* 3번 ~ 20번 접기 */
		for (int i = 3; i <= num; i++) {
			vector<int> next_paper(paper);

			next_paper.assign(paper.begin(), paper.end());
			next_paper.push_back(0); // 무조건 가운데는 0

			int n = (paper.size() / 2);
			paper.at(n)= 1;

			for (int j = 0; j < paper.size(); j++)
				next_paper.push_back(paper[j]);

			paper.clear();
			paper.assign(next_paper.begin(), next_paper.end());
			next_paper.clear();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num;

	cin >> num;
	nFold(num);

	cout << "[";
	for (int i = 0; i < paper.size(); i++) {
		if(i == paper.size()-1)
			cout << paper[i];
		else
			cout << paper[i] << ",";
	}
	cout << "]";
}

https://github.com/youngbinYoon/Baekjoon_Algoritm/blob/master/project1/project1/level3_%EC%A2%85%EC%9D%B4%EC%A0%91%EA%B8%B0.cpp

youngbinYoon/Baekjoon_Algoritm

 

생각보다 쉬운문제였다. 그리고 다른 사람이 푼 코드를 봤을 때 또 새로운 방식을 알아낼 수 있었다.....

0을 넣는 것은 그대로인데 n-1 출력값의 맨 뒤에서부터 -1를 한 값이 그대로 오른쪽 뭉텅이였다... 그렇게 짜면 코드가 좀더 간결해진다.  

for(int i = 1 ; i < n ; i++) {
        answer.push_back(0);
        for(int j = answer.size()-2 ; j >= 0 ; j--) {
            answer.push_back(1-answer[j]);
        }
}