[BOJ - JAVA] 5550 - 헌책방(백트래킹, DP)

# 주소

https://www.acmicpc.net/problem/5550

5550번: 헌책방

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int n,m;
    static int[] arr;
    static int[] ans;
    static boolean[] visit;
    static long max = -50;
	static int[] ten;
	static long sum;
	static int[] dp;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		
		arr = new int[n];
		ans = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = scan.nextInt();
			ans[i] = scan.nextInt();
		}
		dp = new int[m];
		ten = new int[11];
		visit = new boolean[n];
		dfs(0,0,0);
		System.out.println(max);
		scan.close();
	}
	public static void dfs(int start, int index, long sum) {
		if(index == m) {
			for(int i = 0; i < m; i++) {
				for(int j = 1; j <= 10; j++) {
					if(dp[i] == j) {
						ten[j] += 1;
						continue;
					}
				}
			}
			for(int i = 0; i <= 10; i++) {
				sum += (ten[i] - 1) * (ten[i]);
			}
			max = Math.max(sum, max);
			ten = new int[11];
			return;
		}
		for(int i = start; i < n; i++) {
			if(!visit[i]) {
				visit[i] = true;
				dp[index] = ans[i];
				dfs(i + 1, index + 1, sum + arr[i]);
				visit[i] = false;
			}
		}
	}
}

제가 푼 거중에 제일 오래걸렸습니다. 문제 자체는 어려운게 아닌 그리디에 가까운 문제입니다만 계속해서 예제 문제를 출력을 하면 답이 59가 나와서 많이 애먹었습니다.

어제 새벽 1시부터 5시까지 고민하다가 오늘도 12시부터 2시까지 고만하고 학원 마치고 퇴근하고 와서 8시부터 9시까지 보니까 이제야 좀 보이네요. 

이 문제는 예전에 풀어온 것과 똑같이 백트래킹 문제라고 생각하시면 편합니다.

그리고 방문한 인덱스는 들리면 안되기 때문에 boolean배열로 visit을 만들어서 관리를 해야 합니다.

dfs에서 기본적으로 처음부터 탐색할 값을 start, 그리고 갯수는 m개 판매할 것이므로 관련 상수인 index, 그리고 판매 수익인 sum을 dfs의 int 인자로 선언하여 재귀함수 형태로 풀어내는 것이 핵심입니다.

 

바로 밑에 if(index == m) 이 부분은 판매 권수가 4권이 되면 작동하는 곳이므로 거들떠도 안봅니다. 쭉 내려가서

밑에 for문 부터 보시면 int i = start 부터해서 dfs를 가동합니다.

if(!visit[i]) {
visit[i] = true;
dp[index] = ans[i];
dfs(i + 1, index + 1, sum + arr[i]);
visit[i] = false;

이 형태를 눈여겨 보시면 좋겠습니다. 모든 백트래킹의 기본이 되는 부분입니다.

백트래킹은 어려운 것은 전혀 없고 메모리를 조금 많이 잡아먹는다는 단점이 있습니다만 이것 만큼 확실하게 배열의 모든 부분을 탐색할 수 있는 알고리즘 기법은 없다고 생각합니다. 코테에도 자주 나오니 알아주시면 좋겠습니다.

여기서 dfs에 i+1, index +1, sum + arr[i]를 i값이 들어올 때마다 실행을 해주고 index == m이 되면 for문으로 들어갑니다. 위에 이중 for문 보이시죠??

거기서 만약 dp[i] 가 j가 되면 ten배열에 +1씩 하여 ten배열에 담습니다

이 배열은 중복된 값들을 그냥 배열에 담고 중복된 책의 장르가 있을 때마다 +1씩 해주는 것이라 생각하면 됩니다.

그리고 마지막으로 sum 에 ten[i]-1 * ten[i]를 계싼하여 기존의 sum과 비교하여 가장 큰 sum값을 출력하는 것이 목표입니다.

꼭 sum을 max에 담고난 뒤 ten을 초기화 해주셔야 그 다음 로직을 짜는데에 무리가 없습니다.

 

기본적으로 백트래킹은 bottom-up방식을 많이 쓰기 때문에 참고하시면 좋을 것 같습니다.

감사합니다.