#20921 : 그렇고 그런 사이

풀이방법

사용된 것:

그리디 알고리즘

 

2022.02.24

예제를 통해 설명하겠다.

n = 5, k = 6

사람이 5명, 만들어야 하는 관계가 6개인 경우를 보자.

 

일단 초기상태로, 5명에게 오름차순으로 쪽지를 쥐어준다.

 

초기상태(그림판으로 그렸음)

이 상태에서 쪽지를 한 단계에 하나씩만 옮길 것이다.

하나를 옮길 때마다, 그렇고 그런 관계들이 새로 생기게 된다.

그럼 새로 생긴 만큼을 k에서 빼준다.

k가 0이 될 때까지 이를 반복한다.

---

첫 번째 단계이다.

 

현재 k = 6이다.

 

쪽지를 하나만 옮겨서 가장 많은 그렇고 그런 관계를 만드는 방법은 무엇일까?

그렇다. 숫자의 크기가 가장 큰 쪽지를 제일 왼쪽으로 보내는 것이다.

다음과 같이 움직이면 된다.

 

가장 숫자가 큰 쪽지가 제일 왼쪽으로 갔다.

그렇고 그런 관계가 4개 만들어졌다.

(5, 1), (5, 2), (5, 3), (5, 4) 로 4개이다.

쪽지 하나를 옮겨 만들 수 있는 최대의 그렇고 그런 관계인 4개를 만들어도, 목표 개수인 6개를 초과하지 않는다.

k= 6 - 4 = 2로 만들어주고, 다음 단계로 넘어간다.

 

---

 

다음 단계이다.

 

현재 k = 2이다.

 

5번 쪽지의 자리는 가장 왼쪽으로 확정지어졌다.

나머지 4개의 쪽지 중 하나를 움직여 그렇고 그런 관계들을 더 만들어보자.

아까처럼, 4개 중 가장 숫자가 큰 쪽지를 4개 중의 가장 왼쪽으로 보내면 어떻게 될까?

 

자리가 확정되지 않은 쪽지들 중 숫자가 가장 큰 놈인 4번 쪽지를 옮겨주자.

4번 쪽지가 4개 중 가장 왼쪽으로 갔다.

그럼 그렇고 그런 관계가 3개 더 생겼다.

(4, 1), (4, 2), (4, 3) 으로 3개이다.

앗, 문제가 생겼다.

우리가 만들어야 하는 그렇고 그런 관계는 2개인데, 이를 초과한 3개를 만들어버렸다.

틀린 것이다. 움직이기 전으로 되돌리자!

 

이전 상태로 되돌리기!

 

그렇다면 어떻게 해야 할까?

4번 쪽지가 아니라, 4번보다 작은 숫자가 쓰인 쪽지를 옮기면 된다.

 

4번 쪽지를 옮겼을 때에 3개의 그렇고 그런 관계가 만들어졌으니,

3번 쪽지를 옮기면 하나 적은 2개가,

2번 쪽지를 옮기면 둘이 적은 1개가 만들어진다.

 

따라서 3번 쪽지를 왼쪽으로 옮겨주면 된다.

 

자리가 확정되지 않은 4개의 쪽지 중 가장 왼쪽의 위치에, 3번 쪽지를 가져다놓았다.

그렇고 그런 관계가 2개 생겼다.

(3, 1), (3, 2) 로 2개이다.

우리의 목표 개수인 2개를 딱 맞추어 만들었다!

k = 2 - 2 = 0으로 업데이트한다.

 

k값이 0이 되었으니, 우리는 목표를 이루었다.

현재 쪽지의 위치를 화면에 출력해주면 문제 해결이다.

 

5 3 1 2 4

 

---

 

이러한 알고리즘을 코드로 짜주기만 하면 된다.

쪽지를 특정 자리로 옮겨놓을 때마다, 자리보다 오른쪽인 쪽지들이 자동으로 오른쪽으로 한 자리씩 옮겨야 하므로, ArrayList를 사용하였다.

 

가장 앞자리부터, 즉 한 번에 가장 많은 그렇고 그런 관계가 새로 생성되는 경우부터 차근차근 점검해나가기 때문에,

그리디 알고리즘이 사용되었다고 볼 수 있다.

 

코드

Java(2022.02.24)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	static int n, k;	//사람 수, 그렇고 그런 사이의 수
	static ArrayList<Integer> people;	//각 사람이 들고 있는 쪽지번호
	static StringTokenizer st;
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		sb = new StringBuilder();
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		//배열 생성 및 초기화
		people = new ArrayList<Integer>();
		for(int i = 0; i<n+1; i++) {
			people.add(i);
		}
		//k값에 맞게 쪽지번호 바꾸기
		//새 관계가 생길 때마다, 생긴 개수만큼을 k에서 빼준다
		for(int i = 1; i<n+1; i++) {
			//k값이 0이 되었다면 필요한 만큼 다 만든 것이므로 관계만들기를 종료
			if(k ==0) break;
			//아직 만들 관계가 남았다면 아래와 같은 과정을 통해 더 만들기
			if((n-i)>k) {
				people.remove(i+k);
				people.add(i, (k+1));
				break;
			}
			
			else {
				people.remove(n);
				people.add(i, n-(i-1));
				k -= (n-i);
			}
		}
		//결과 출력
		for(int i = 1; i<n+1; i++) {
			sb.append(people.get(i));
			if(i < n)sb.append(" "); 
		}
		System.out.println(sb);

	}

}