[SWEA / Java] 1244번: 최대상금 (D3)

문제 풀이 날짜: 2023.05.20
포스트 작성일: 2023.05.21

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

Software Expert Academy 1244번: 최대상금 (D3) (문제 링크)

 

키워드

완전탐색(백트랙킹)

 

풀이 접근법

• 각 교환 횟수마다의 최댓값을 기록한다고 해도 그것이 마지막까지 최적해임을 보장할 수는 없다. 따라서 완전탐색으로 풀이하였다.
  • 최대 자릿수가 6이고 최대 교환 횟수가 10회이므로 백트랙킹으로 풀어도 시간초과가 되지 않는다.
• 여기서 주의해야 할 점은, 배열 요소의 수는 최대 6개인데 수를 10회 교체하라고 하면, 이미 바꿨던(swap) 부분을 또 다시 바꿔야 한다. 따라서 6번째 값을 가리킬 때는 다시 현재 인덱스(lastIndex)를 0으로 되돌려서 탐색한다.
• 입력 패널이 “00000”일 때나 패널의 교환 결과가 "09"여서 0을 제거해야 하는 경우 등을 주의해야 한다.

 

코드

import java.io.*;

public class SWEA1244 {

	private static final int MAX_LENGTH = 6;
	private static int answer = -1;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			String temp[] = br.readLine().split(" ");
			
			char[] prize = temp[0].toCharArray();
			int count = Integer.parseInt(temp[1]);
		
			DFS(prize, count, 0, 0);
			
			if(answer == -1) { //교환할 수 없는 상황이라면
				answer = Integer.parseInt(temp[0]);
			}
			
			sb.append("#" + test_case + " ").append(answer).append('\n');
		}
		
		System.out.print(sb);
	}
	
	public static void DFS(char[] prize, int count, int depth, int lastIndex) {
				
		if(depth == count) {
			String result = String.valueOf(prize);
			
			answer = Math.max(Integer.parseInt(result), answer);
			
			return;
		}
		
		if(lastIndex % (MAX_LENGTH - 1) == 0) {
			lastIndex = 0;
		}
		
		for(int i = lastIndex; i < prize.length - 1; i++) {
			for(int j = i + 1; j < prize.length; j++) {
				//i번째 수와 j번째 수를 swap
				char temp = prize[i];
				prize[i] = prize[j];
				prize[j] = temp;
				
				//dfs 호출
				DFS(prize, count, depth + 1, lastIndex + 1);
				
				//원복
				temp = prize[i];
				prize[i] = prize[j];
				prize[j] = temp;
			}
		}
		
		return;
	}

}

---

어렵지 않은 백트랙킹 응용 문제라고 생각한다. 다만 여기서 재귀의 depth가 지정된 count까지 도달하지 못하는 경우(answer == -1) 가장 처음의 입력값을 가지도록 해주었다. count까지 도달하지 못하는 이유로는 여러 가지가 있지만 정확한 해결방안을 알아내지 못해 모호하게 예외처리를 하게 되었는데, 차후 복습하며 코드를 정확하게 개선해야겠다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day7/SWEA1244.java