글 읽기 - 결정문제로 변환해서 풀면 안된는건가요?

filot 7년 전 0

최소로 수로 지붕을 채울 수 있는 경우의 수를 구해서

당시에 선택된 color에 해당하는 페인트의 비용을 더해 주었는데

(페인트는 비용이 적게 드는 것부터 선택하는게 좋으니 정렬을 해버렸습니다.)

틀리다고 하네요.. ㅠㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main1 {
	static int N;
	static int M;
	static List[] adjList;	
	static int[] COST_OF_PAINT;
	static int[] COLOR_OF_ROOF;
	
	public static void main(String[] args) throws Exception {		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		
		N = Integer.parseInt(reader.readLine());		
		adjList = new List[N + 1];
		COLOR_OF_ROOF = new int[N + 1];
		
		for (int i = 1; i <= N; i++)
			adjList[i] = new ArrayList<Integer>();
		
		for (int i = 1; i <= N - 1; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			adjList[u].add(v);
			adjList[v].add(u);
		}
		
		M = Integer.parseInt(reader.readLine());
		COST_OF_PAINT = new int[M + 1];
		
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 1; i <= M; i++)
			COST_OF_PAINT[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(COST_OF_PAINT);
		
		// 이진탐색
		int begin = 1;
		int end = M;
		int color = 0;
		
		while (begin <= end) {
			int middle = (end + begin) / 2;
			
			if (solve(middle)) {
				color = middle;
				end = middle - 1;
			}
			else
				begin = middle + 1;
		}
		
		int cost = 0;
		for (int i = 1; i <= N; i++)
			cost += COLOR_OF_ROOF[i];
		
		writer.println(cost);
			
		writer.close();
		reader.close();
	}
	
	// m : 1 ~ m까지의 color
	// m개의 color를 이용해서 지붕을 채울 수 있는 경우가 존재하는가?
	public static boolean solve(int m) {		
		Queue<Integer> QUEUE = new ArrayDeque<Integer>();
		
		Arrays.fill(COLOR_OF_ROOF, 0);
		COLOR_OF_ROOF[1] = 1;
		QUEUE.offer(1);
		
		while (!QUEUE.isEmpty()) {
			int u = QUEUE.poll();
			
			List<Integer> list = adjList[u];			
			for (Integer v : list) {
				if (COLOR_OF_ROOF[v] == 0) {
					COLOR_OF_ROOF[v] = COLOR_OF_ROOF[u] % m + 1;
					QUEUE.offer(v);
				}
				
				else if (COLOR_OF_ROOF[u] == COLOR_OF_ROOF[v])
					return false;
			}
		}
		
		return true;
	}
}

zlzmsrhak 7년 전 1

일단 반례입니다. 알고리즘만 봤을 때는 제가 예상한 출력은 303이고, 답은 204입니다.

트리는 항상 2개의 색으로 칠하는 것이 가능합니다.

filot 7년 전 0

감사합니다.

제가 정답이 경우에 해당하는 경우를 저장하지 않았네요.

그런데도 제출한 하면 틀리네요.

뭔가 예외 케이스가 있을 듯 한데.. 찾기가 쉽지 않네요.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static List[] adjList;
    static int[] COST_OF_PAINT;
    static int[] COLOR_OF_ROOF;

    public static void main(String[] args) throws Exception {
    	
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        N = Integer.parseInt(reader.readLine());
        adjList = new List[N + 1];
        COLOR_OF_ROOF = new int[N + 1];

        for (int i = 1; i <= N; i++)
            adjList[i] = new ArrayList<Integer>();

        for (int i = 1; i <= N - 1; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            adjList[u].add(v);
            adjList[v].add(u);
        }

        M = Integer.parseInt(reader.readLine());
        COST_OF_PAINT = new int[M + 1];

        StringTokenizer st = new StringTokenizer(reader.readLine());
        for (int i = 1; i <= M; i++)
            COST_OF_PAINT[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(COST_OF_PAINT);

        // 이진탐색
        int begin = 1;
        int end = M;
        int color = 0;

        while (begin <= end) {
            int middle = (end + begin) / 2;

            if (solve(middle)) {
                color = middle;
                end = middle - 1;
            }
            else
                begin = middle + 1;
        }

        int cost = 0;
        for (int i = 1; i <= N; i++)
            cost += COST_OF_PAINT[COLOR_OF_ROOF[i]];

        writer.println(cost);

        writer.close();
        reader.close();
    }

    // m : 1 ~ m까지의 color
    // m개의 color를 이용해서 지붕을 채울 수 있는 경우가 존재하는가?
    public static boolean solve(int m) {
        Queue<Integer> QUEUE = new ArrayDeque<Integer>();

        int[] colorOfRoof = new int[N + 1];

        colorOfRoof[1] = 1;
        QUEUE.offer(1);

        while (!QUEUE.isEmpty()) {
            int u = QUEUE.poll();

            List<Integer> list = adjList[u];
            for (Integer v : list) {
                if (colorOfRoof[v] == 0) {
                	colorOfRoof[v] = colorOfRoof[u] % m + 1;
                    QUEUE.offer(v);
                }

                else if (colorOfRoof[u] == colorOfRoof[v])
                    return false;
            }
        }

        System.arraycopy(colorOfRoof, 0, COLOR_OF_ROOF, 0, N + 1);

        return true;
    }
}

zlzmsrhak 7년 전 1

제가 올린 예제의 답은 204인 것 같습니다.

2,3번을 각각 2, 3번 색으로 칠하고, 나머지를 1번색으로 칠하면 204가 나옵니다

filot 7년 전 1

에휴잘안되네요.. 푸신분 힌트라도 좀 얻을 수 없을까요?

zlzmsrhak 7년 전 1

트리DP를 사용하고, 테이블로는 D[v][c] : v번째 정점을 c로 칠했을 때, v의 부트리를 칠하는 최소 비용

으로 점화식을 세워보세요

filot 7년 전 0

DP군요.. 넵 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

결정문제로 변환해서 풀면 안된는건가요?

filot 7년 전 0

zlzmsrhak 7년 전 1

filot 7년 전 0

zlzmsrhak 7년 전 1

filot 7년 전 1

zlzmsrhak 7년 전 1

filot 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말