글 읽기 - 분해하는 방식은 틀렸나요? (+ 2번 예제 864 만드는 순서라도...)

rlaalswo01 6년 전 0

풀이 과정 등을 보지 않고 풀어보려는데 내공이 부족해 고생 중이네요.

고민한 끝에

1. 목적으로 하는 수퍼 파일을 만들기 위한 병합 과정에서 큰 파일을 포함한 병합 파일을

병합에 다시 사용할 때마다 큰 비용을 반복적으로 누적하는 효과가 발생한다.

2. 마지막 덩어리를 만들 때 두 개의 덩어리가 병합되며, 그 비용은 늘 모든 항의 크기의 합과 같다.

1 + 2. 병합이 완료된 마지막 덩어리를 만들기 전의 두 덩어리가 크지 않도록 한다.

(큰 것이 있다면 큰 것이 만들어지면서, 또 다시 그것이 최종 덩어리를 만드는데 사용되면서 큰 비용을 발생시킴)

결론.

1. 두 개의 덩어리로 나눠질 때, 가장 균등한 두 덩어리로 나뉘어야 한다.

(한 쪽이 작아지면 한 쪽이 커짐.)

2. 나눈 양 조각을 계속 같은 방식으로 분해할 수 있다.

3. 분해하여 발생하는 두 조각의 크기의 합

=현재 덩어리를 만들 때 발생한 병합 비용

=현재 덩어리 크기

=> 큰 덩어리를 균등한 두 조각으로 분해하며 비용을 누적한다.

이런 아이디어로 진행했는데, 2번 예제 입력시 865가 나오네요.

한 끗 차이라, 제 아이디어가 전혀 틀린 아이디어인데 운이 좋게

정답에 가까운 수가 나왔을 뿐인건지, 아이디어는 맞는데 코드의 디테일이

틀린 건지 궁금합니다.

#include <iostream>

using namespace std;
int tc;
int k;
int files[501];                    // 입력값
int cost = 0;
int inf = 1e8;

int sums[501];    //0~500        //1~각 인덱스까지의 입력값의 누적합


int diff(int a, int b)        //두 정수의 차를 반환
{
	if (a>b)
		return a - b;
	else
		return b - a;
}


void sorting(int s, int e)    //처음 시작할 때, 0과 k를 넣는다. (첫 조각은 1~k에 존재한다.)
{

	if (s + 1 == e)           //s까지 조각에서 제외되고 그 다음부터 현재 조각이므로 항이 하나라 분해 불가
		return;

	int minimum = inf;        // 분해되어 생길 양 조각의 크기 차이 최솟값 갱신을 위해 큰 수로 초기화
	int division;             // 재귀 호출을 위해 분할점(?) 인덱스를 저장
    
    
    // 인덱스 division은 나누어질 왼쪽 조각의 마지막이고, 그 다음부터 오른쪽 조각이 시작되므로
    // 왼쪽 조각의 시작 전칸인 s보다 크고, 오른쪽 조각의 마지막 보다는 작아야 한다.
	for (int i = s+1; i < e; i++)        
	{
		int tempsum1 = sums[i] - sums[s];    // s 다음부터 i까지의 누적합
		int tempsum2 = sums[e] - sums[i];    // i 다음부터 e까지의 누적합
		if (diff(tempsum1, tempsum2) < minimum)    
		{
			minimum = diff(tempsum1, tempsum2);
			division = i;
		}// 현재 분해하고자 하는 덩어리를 가장 균등한 두 조각으로 나누는 곳 찾기
	}

	//cost += (sums[division] - sums[s]) + (sums[e] - sums[division]);
    cost+= sums[e] - sums[s];    // 위 식과 같음.
    // 현재 덩어리를 나눔으로 생기는 두 조각의 크기의 합
    // = 현재 덩어리를 위해 두 조각을 합치면서 발생했던 비용과 같음
    // = 현재 덩어리 크기.

	sorting(s, division);    //왼쪽 조각을 다시 재귀호출로 분해
	sorting(division, e);    //오른쪽 조각을 다시 재귀 호출로 분해


	return;
}

int main()
{
	cin >> tc;
	for (int t = 0; t<tc; t++)
	{
		cin >> k;
		cost = 0;
        
		sums[0] = 0;        //index 0은 비어있고 1~k항까지 입력이 채워진다.
        files[0] = 0;
		for (int i = 1; i <= k; i++)
		{
			cin >> files[i];
			sums[i] = sums[i - 1] + files[i];
		}                //자기보다 왼쪽 항들에 대한 누적 값을 sums에 저장

		sorting(0, k); // 매개변수 s 다음 칸부터 조각이 시작하여 1~k 조각을 분해한다.
		cout << cost << endl;

	}

	return 0;

}

doju 6년 전 2

합이 비슷한 두 그룹으로 나눈다는 것은 좋은 발상이지만 최소 비용을 구하지는 못할 수 있습니다.

[21  14  17  32] -> [21  14][17  32] : +84
[21  14][17  32] -> [21][14][17  32] : +35
[21][14][17  32] -> [21][14][17][32] : +49
total 168

[21  14  17  32] -> [21  14  17][32] : +84
[21  14  17][32] -> [21][14  17][32] : +52
[21][14  17][32] -> [21][14][17][32] : +31
total 167

rlaalswo01 6년 전 0

뭔가 스스로 수학적인 의미를 찾아 해결하려 하다가 걍 쪼개면서

알아서 최솟값 반환하라는 식으로 하니 풀리네요 ㅎㅎ

허무하기도 하지만 뭔가 이게 진짜 DP의 미학이구나 싶었습니다.

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

문제

문제

출처

ICPC

분해하는 방식은 틀렸나요? (+ 2번 예제 864 만드는 순서라도...)

rlaalswo01 6년 전 0

doju 6년 전 2

rlaalswo01 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말