[SWEA] [S/W 문제해결 응용] 2일차 - 최대 상금

문제

퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다.

우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다.

예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자.

교환전>

처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다.
 

다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다.

정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다.

숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다.

위의 예에서와 같이 최종적으로 숫자판들이 8,8,8,3,2의 순서가 되면 88832원의 보너스 상금을 획득한다.

여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.

다음과 같은 경우 1회의 교환 횟수가 주어졌을 때 반드시 1회 교환을 수행하므로 결과값은 49가 된다.

94의 경우 2회 교환하게 되면 원래의 94가 된다.

정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.

 

풀이방법

맨 앞자리부터 가장 큰수로 교체해주는 문제이지만 몇가지 반례를 찾는다.

 

1) 교체해야할 가장 큰 수가 여러개 존재할 경우

예) 2737 1 -> 인덱스가 높은 값으로 교체해준다.

 

2) 1)의 방식을 적용했을 때 결과값이 최적이 아닐경우

예) 32888 2 경우 1)의 방식을 적용해 가장 뒤에 있는 큰수와 교체하게 되면 88823가 된다.

하지만 최적값은 88832이다.

-> 초기 32888에서 3과 교체할 수를 찾을 때 *교체할 수 있는 가장 큰 수가 여러개 존재할 경우,  *총 교체할 수 있는 횟수 n과 3에서 n만큼 인접한 수 중에 3보다 작은 수가 있는 경우에 한해서 교체할 수 있는 가장 큰 수 중 교체해야할 작은 수만큼의 앞의 수와 교체한다.

즉, 32888에서 교체횟수는 2이고 교환할 수 있는 수는 32888, 세개가 존재한다. 이 때, 3과 n만큼 인접한 수 중 3보다 작은 수는 32888, 한 개가 존재한다. 따라서 한 개만큼의 수 앞의 32888, 8과 교체한다. 

 

3) 최적의 값을 구한 뒤에 교체 횟수가 남은 경우

문제에서는 n만큼의 교체가 모두 이루어져야한다고 명시되어있다.

하지만 이미 최적의 값을 구한 뒤이기 때문에 최대한 값의 변화가 없어야한다.  두 가지 경우를 생각하면

 

(1) 남은 횟수가 짝수일 경우 -> 교체가 두 번 이루어지기 때문에 전체 값의 변화가 없으므로 그대로 출력

 

(2) 남은 횟수가 홀수일 경우 -> 무조건 교체가 이루어져야한다. 이 또한 두가지 경우로 생각할 수 있다.

a. 같은 수가 존재할 경우 -> 같은 수끼리 교체해 값의 변화가 없도록한다.

b. 같은 수가 존재하지 않을 경우 -> 가장 작은 두자리 수 a[n-2], a[n-1]과 교체해 값의 변화를 최소한으로 줄인다.

 

소스코드

package samsung;

import java.util.*;

public class s_1244 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			String s = sc.next();
			int n = sc.nextInt();
			int[] a = new int[s.length()];
			
			for(int i = 0; i < s.length(); i++) {
				a[i] = s.charAt(i) - '0';
			}
			
			for(int i = 0; i < a.length; i++) {
				ArrayList <Integer> l = new ArrayList();
				int cnt = 0;
				int max = a[i];
				for(int j = i + 1; j < a.length; j++) {
					if(a[i] < a[j]) {
						max = Math.max(max, a[j]);
					}
				}
				for(int j = i + 1; j < a.length; j++) {
					if(a[j] == max) {
						l.add(j);
					}
				}
				for(int j = i + 1; j < n; j++) {
					if(j >= a.length)
						break;
					if(a[j] < a[i]) {
						cnt++;
					}
				}
				if(l.size() == 1) {
					int tmp = a[i];
					a[i] = a[l.get(0)];
					a[l.get(0)] = tmp;
					n--;
				}
				if(l.size() > 1) {
					int tmp = a[i];
					a[i] = a[l.get(l.size() - 1 - cnt)];
					a[l.get(l.size() - 1 - cnt)] = tmp;
					n--;
				}
				if(n < 1)
					break;
			}
			if(n % 2 == 1) {
				int flag = 0;
				for(int i = 0; i < a.length; i++) {
					for(int j = i + 1; j < a.length; j++) {
						if(a[i] == a[j])
							flag = 1;
					}
				}
				if(flag == 0) {
					int tmp = a[a.length - 1];
					a[a.length -1] = a[a.length - 2];
					a[a.length -2] = tmp;
				}
			}
			
			System.out.print("#" + t + " ");
			for(int i = 0; i < a.length; i++) {
				System.out.print(a[i]);
			}
			System.out.println();
		}
	}
}

 

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE

SW Expert Academy