[백준/c++] 21313 - 문어

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

21313번: 문어

---

1) 풀이

사전순으로 제일 앞서는 n길이의 수열을 만드는 문제이다.

1번과 2번, 2번과 3번.... 1) 앞뒤번호로 이어진 문어는 서로 같은 번호의 손을 잡아야하고

2) 반드시 한 손으로만 손을 잡으며 3)이미 사용한 손으로 다른 문어의 손을 잡을 수 없다.

 

일단, 문어들이 잡은 손의 번호를 저장할 벡터를 준비한다.

그리고 각 문어들의 손 번호 1~8번이 저장된 배열(손번호 배열)을 준비한다.

(인덱스나 뭐 그런 걸로 해도 될 것 같은데, 헷갈릴 것 같아서 그냥 따로 배열을 만들었다😂)

 

그리고, 첫번째부터 n번째까지 각 문어를 돌아가면서 사용한 손을 확인한다.

이때, 사전순으로 가장 앞서는 것을 벡터에 집어넣어야 하므로, 손번호 배열의 첫 인덱스부터 사용한 손인지

확인해보되, 만약 사용한 손이 아니라면 바로 벡터에 집어넣고 다음 문어로 넘어간다.

이전에 사용한 손은 제일 최근에 벡터에 삽입된 값, 즉 벡터의 back으로 확인한다.

 

딱히 어려운 점이 없는 문제이지만, 굳이 유의할 점을 적어보자면

벡터에 아무값도 들어가지 않은 상태에서는 예외처리를 해줘야 하고,

마지막 문어와 첫번째 문어가 사전순으로 제일 앞선 같은 번호의 손을 잡도록 해줘야 한다.

 

오랜만에 푼 문제가 너무 귀욤귀욤한 문제라 기분이 조탕 ヾ(≧▽≦*)o

 

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
vector<int>v; //문어들이 어떤 손을 잡았는지 숫자를 집어넣는 벡터.
int arr[8] = { 1,2,3,4,5,6,7,8 }; //각 문어의 손
int n;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		if (v.empty()) { //아무도 손잡은 문어가 없을 때. 즉, 1번 문어가 손을 잡을 차례.
			v.push_back(1); //사전순으로 제일 앞서야 하므로 1을 집어넣고 다음 문어로 넘어감.
			continue;
		}
		for (int j = 0; j < 8; j++) {
			if (i == n - 1 && v[0] == arr[j]) continue; //제일 마지막 문어일때 첫번째문어가 이미 사용한 손이면 넘어감
			if (v.back() != arr[j]) { //이전 문어가 사용한 손이 아니면
				v.push_back(arr[j]); //벡터에 손을 집어넣음
				break;
			}
		}
	}
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' '; 
	}
}

3) 참고자료