글 읽기 - 풀이 방식 확인좀 부탁드립니다!

tngus1140 2년 전 0

dp로 말고 더블 링크드 리스트를 사용하여

두 행렬을 곱했을 때 최소 값이 나오는 포인터 둘을 저장하여

계속해서 더해주도록 했습니다.

500개의 데이터를 넣어도 잘 처리되며 틀리다고 나오는데

어떤 부분에서 틀린지 궁금합니다.

위 그림 처럼 가장 최소가 되는 조합을 찾아 하나로 묶은 뒤(7,2 x 2,5 = 7,5) 최종 1개가 남을 때 까지 반복하는 방식입니다.

dp방식으로도 풀 예정인데

혹시라도 이 풀이법이 어떤 문제가 있는지 알려주시면 감사하겠습니다!

#include <iostream>
#include <limits.h>

using namespace std;

class procPtr {
public:
	void init(int tR, int tC) {
		r = tR; c = tC;
		prevPtr = nextPtr = nullptr;
	}

	bool nextValid() {
		return nextPtr != nullptr;
	}
public:
	procPtr* prevPtr, * nextPtr;
	int r, c;
};

procPtr procession[550];

#define NULL_PROC &procession[0]

int solve() {
	if (procession[1].nextPtr == nullptr) {
		return 0;
	}

	// 가장 적은 값이 나오는 행렬 곱 찾기
	procPtr* now = &procession[1];

	// LP = Least Product
	int LP = INT_MAX, tempLP;
	procPtr* LP_ptr1 = NULL_PROC;
	procPtr* LP_ptr2 = NULL_PROC;

	while (now->nextValid()) {
		tempLP = now->r * now->c * now->nextPtr->c;

		if (tempLP < LP) {
			LP = tempLP;
			
			LP_ptr1 = now;
			LP_ptr2 = now->nextPtr;
		}

		now = now->nextPtr;
	}

    // 두 포인터를 하나로 합침
	LP_ptr1->nextPtr = LP_ptr2->nextPtr;
	if (LP_ptr2->nextValid()) {
		LP_ptr2->nextPtr->prevPtr = LP_ptr1;
	}
	LP_ptr1->c = LP_ptr2->c;

	return LP + solve();
}

int main(void) {
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, r, c;
	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> r >> c;
		procession[i].init(r, c);
	}

	for (int i = 2; i <= N; i++) {
		procession[i - 1].nextPtr = &procession[i];
		procession[i].prevPtr = &procession[i - 1];
	}

	cout << solve();
	return 0;
}

djm03178 2년 전 1

그 방법으로는 최적해를 구할 수 없고, 그래서 dp를 해야 합니다.

tngus1140 2년 전 0

방금 dp로 풀어봤는데 저렇게 최적해를 구하는게 아니더라구요

이해됬습니다!

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

문제

문제

출처

ICPC

풀이 방식 확인좀 부탁드립니다!

tngus1140 2년 전 0

djm03178 2년 전 1

tngus1140 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말