백준 20921번: 그렇고 그런 사이

 

풀이

  설명이 부족한 것 같아서 예제를 들고와봤다.

  입력 1처럼 N = 4, K = 2가 주어지면 1, 2, 3, 4의 숫자 중에서 왼쪽의 숫자가 오른쪽의 숫자보다 큰 경우의 수가 2개 있어야 한다. (ex: 3 1 2 4 또는 1 4 2 3 등) 다양한 풀이 방법이 있겠지만 나는 N 크기로 오름차순 정렬이 되어있는 배열을 먼저 만든 다음, 배열의 끝에서부터 K번 만큼 왼쪽 숫자와 위치를 바꾸도록 코드를 작성했다. 여기서 주의할 점은 입력 2처럼 K가 N보다 더 크게 주어지는 상황인데, 이럴 때에는 이미 N-1번의 반복을 통해서 가장 왼쪽으로 간 최대값을 다시 오른쪽과 스왑하면 안되기 때문에 반복문으로 왼쪽 요소들을 스왑 대상에서 제외시켜주는 작업을 추가해주었다.

 

코드

#include <iostream>
#define MAX 4243
using namespace std;

int N, K;
int u[MAX];

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) u[i] = i+1;

	int cnt = 0;
	for (int n = 1; n < N; n++) {
		for (int i = N - 1; i > n - 1; i--) {
			if (cnt >= K) break;

			int temp = u[i];
			u[i] = u[i - 1];
			u[i - 1] = temp;
			cnt++;
		}
		if (cnt >= K) break;
	}

	for (int i = 0; i < N; i++) cout << u[i] << " ";

}