[백준온라인] 13018번 특이한 수열

백준 13018번 - 특이한 수열

🔗 문제 링크: https://www.acmicpc.net/problem/13018

13018번: 특이한 수열

📝 문제 요약

• 수열 A의 길이는 n
• 1 이상 n이하의 정수가 빠짐없이 모두 등장해야 하며, 각 수는 한 번만 등장해야 함
• 1 ≤ i ≤ n 인 i에 대해 gcd(i, A[i]) > 1을 만족하는 i가 정확히 k개여야 함
  

  ---

  
  

🧷 문제 분류

• 애드혹
• 정수론
  

  ---

  
  

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_13018.cpp

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
93897156	cbkpar	13018	맞았습니다!!	2412 KB	8 ms	C++17	651 B

---

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int iN, iK;
	cin >> iN >> iK;

	if (iK == iN)
	{
		cout << "Impossible" << "\n";
		return 0;
	}

	vector<int> vecNum(iN + 1, 0);
	for (int i = 1; i <= iN; ++i)
	{
		vecNum[i] = i;
	}

	int iRest = iN - 1 - iK;

	for (int i = 2; i <= iN; i += 2)
	{
		if (iRest < 2)
		{
			break;
		}
		iRest -= 2;
		swap(vecNum[i], vecNum[i + 1]);
	}

	if (iRest == 1)
	{
		swap(vecNum[1], vecNum[iN]);
	}

	for (int i = 1; i <= iN; ++i)
	{
		cout << vecNum[i] << (i == iN ? "\n" : " ");
	}
	return 0;
}

---

💡 풀이 방법

🔍 문제 접근

• 인접한 수를 적절히 교환하여 문제를 해결.
• 가능하지 않은 경우 Impossible을 출력해야 하며, 가능한 경우 그 수열을 출력.

🧠 핵심 아이디어

• 1은 항상 gcd값이 1이 나온다.
• k 값이 n과 같은 경우는 Impossible 처리.
• gcd(n, n+1) = 1이라는 원리를 이용 

📌 gcd(n, n+1) = 1 수학적 증명 (유클리드 호제법)

gcd(n, n+1)은 유클리드 호제법을 이용해 다음과 같이 유도할 수 있습니다.

gcd(n, n+1) = gcd(n+1 - n, n) = gcd(1, n) = 1

즉, 연속된 두 수는 그 차이가 1이므로 항상 최대공약수는 1이 됩니다.

⚙️ 구현 방식

1. 1부터 N까지의 수를 초기 배열에 채운다. -> gcd(i,arr[i]) 만족하는 개수는 N-1개
2. N-1개에서 K개를 만족하도록 바꾸기 위한 개수를 계산한다 (N-1-K) = R개
3. 배열의 2번째부터 2칸씩 뛰며 순회하며 R이 2 이상 일경우 배열의 다음 값과 자리를 바꾸고 R을 2 빼준다.
4. 최종적으로 R값이 1 남은 경우, 처음과 마지막을 swap.
5. 최종 배열을 출력.

✅ 시간 복잡도

• O(N): 한 번의 루프만으로 swap 진행
• 입력 크기가 작아 실질적으로 상수 시간 수준