글 읽기 - 문제 접근방법좀 알려주실 수 있나요!?

dokrsky 8년 전 0

지금 다이나믹으로 접근해보고 싶은데, 도저히 안떠오르네요 ㅜㅜ

1 2 3 4 -> 3 1 1 0 으로 만들기 위해서

2 2 3 4 -> 3 2 3 4 -> 3 1 2 3 -> 3 1 1 2 -> 3 1 1 1 -> 3 1 1 0 해서 총 6번인건 알겠는데, 이걸 dp로 접근하기가 힘듭니다 ㅠㅠ

도와주세요 ! ㅠ

alohajihwan 8년 전 2

dp로 접근하려면 먼저 반복되는 경우가 언제 발생하는지 봐야 합니다.

이 문제를 풀기 위해서 알아야할 핵심은 각각의 index에서 (출발지 - 도착지) 가 같은 부호 이면 같은 그룹이 된다는 것입니다.

그룹 각각을 처리할 때 이제 dp가 사용 됩니다. 처리하는 방법은 그룹 내에서 가장 작은 값(절대값) 을 정하고 그만큼을 그룹 전체에 빼준 다음

가장 작은 값을 제외한 그룹에서 다시 그 과정을 거치는 것 입니다.

alohajihwan 8년 전 0

예를 들어

1 1 1 1 1

5 3 1 3 5

가 주어지면 일단 모든 index는 -로 부호가 같아 하나의 그룹입니다. 이제 이 그룹을 처리할 때 차이 값이 가장 작은 index를 찾습니다.

이 경우는 3번째 경우이지요. 그 다음 3번째 index를 제외한 첫번째~두번째, 4번째~5번째 그룹을 다시 위의 과정을 거치게 합니다.

결국 하나의 그룹내에서 dp 반복이 생겨 dp로 풀 수 있는 것입니다.

dokrsky 8년 전 0

alohajihwan 님 답변감사합니다!!

밑의 코드는 제가 작성한 건데, 틀렸습니다 가 나옵니다 ㅠㅠ

어디가 잘못된걸까요?

#include <iostream>
#pragma warning(disable:4996)

int num[80];
int ans[80];
int d[80];
int N;

int main() {
	scanf("%d", &N);

	for (int i = 0; i < N; ++i) {
		scanf("%d", &num[i]);
	}
	for (int i = 0; i < N; ++i) {
		scanf("%d", &ans[i]);
		// 들여쓰기의 횟수를 계산
		d[i] = num[i] - ans[i];
	}

	int index = 0;
	int cnt = 0;
	while (index < N) {
		bool flag = false;
		int v = d[index];
		flag = v < 0 ? true : false; // 음수면 true, 양수면 false

		int result = v;
		if (flag) {
			// 그룹을 지정하기 위해서 음수그룹을 찾음 
			while (v < 0 && index < N) {
				if (result > v) {
					result = v;
				}
				index++;
				v = d[index];
			}
			// 만약 -3, -5, -1 이라면 가장 큰 연속 된 그룹내에선 5번을 누르면 됨
			cnt += (result * -1);
		}
		// 위의 과정과 같이 1 9 5 라면 9번을 누르면 됨
		else {
			while (v >= 0 && index < N) {
				if (result < v)
					result = v;
				index++;
				v = d[index];
			}
			cnt += result;
		}
	}

	printf("%d\n", cnt);
	return 0;
}

alohajihwan 8년 전 0

// 만약 -3, -5, -1 이라면 가장 큰 연속 된 그룹내에선 5번을 누르면 됨

이 가정이 잘못 됬습니다. 만약 인풋이

1 1 1 1 1

5 3 2 3 2 로 주어지면

일단 3번째 부호를 맞춰줘서 2 2 2 2 2가 됩니다(1) 그다음 이제 3번째 수를 건들면 안되기 때문에 1~2번째 4~5번째 그룹으로 나눕니다

그다음 2 2

5 3

2 2

5 3

두개의 그룹으로 나눠서 생각해야 하기 때문에 답이 7 나옵니다.

결국 이 문제를 풀기 위해서는 그룹을 나눠서 생각하는 분할정복(DP)를 사용해야 합니다.

dokrsky 8년 전 0

alohajihwan님 감사합니다! 제출했더니 맞았습니다가 뜨네요 ㅎㅎ 정말 감사드립니다!!!!

grands 7년 전 0

위에 테케

5
1 1 1 1 1
5 3 2 3 2

답이 5아닌가요?

tofle 7년 전 0

1 1 1 1 1

5 3 2 3 5 라고 착각하신듯

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

문제

문제

출처

ICPC

문제 접근방법좀 알려주실 수 있나요!?

dokrsky 8년 전 0

alohajihwan 8년 전 2

alohajihwan 8년 전 0

dokrsky 8년 전 0

alohajihwan 8년 전 0

dokrsky 8년 전 0

grands 7년 전 0

tofle 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말