글 읽기 - 계단오르기와 동일한 dp적용후 저

shw8581 7년 전 0

어차피 계단이랑 포도주랑 3개이상은 안되어 그냥 계단이랑 같은 dp를 적용했는데 차이라곤 마지막계단 밟는거라 각 dp에서 정렬을 사용해서 젤큰값으로 이끌어냈는데요 틀렸다고 하네요.. 뭐가틀린건가요??

#include<stdio.h>
int sorted[10001];
int max(int a, int b) {
	return a > b ? a : b;
}
void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left; j = mid + 1; k = left;

	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}
	if (i > mid)
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	for (l = left; l <= right; l++)
		list[l] = sorted[l];
}
void merge_sort(int list[], int left, int right) {
	int mid;
	
	if (left < right) {
		mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid+1, right);
		merge(list, left, mid, right);
	}
}

int main(void){
	int num[10001] = {};
	int dp[10001] = {};
	
	int tc;
	scanf("%d", &tc);

	for (int i = 1; i <= tc; i++) {
		scanf("%d", &num[i]);
		if (num[i] > 1000) {
			i--;
			continue;
		}
	}	
	for (int j = 1; j <= 3; j++) {
		if (j != 3)
			dp[j] = dp[j - 1] + num[j];
		else
			dp[j] = max(num[j] + dp[j - 2], num[j] + num[j - 1]);
	}
	for (int k = 4; k <= tc; k++) {
		dp[k] = max(num[k] + num[k - 1] + dp[k - 3], num[k] + dp[k - 2]);
	}
	merge_sort(dp, 0, tc);
	printf("%d\n", dp[tc]);
	
}

devetude 7년 전 0

bottom-up 방식으로 구현하신 경우 다음과 같이 코딩하실 수 있습니다.

코드를 살짝 유연하게 작성하시면, 병합 정렬은 사용하지 않으셔도됩니다.

코드의 일부만 작성해보았습니다.

참고로 cache는 메모이제이션에 필요한 배열이고, input은 입력 값들을 저장하고 있는 배열입니다.

cf) top-down 방식으로 구현 할 경우엔... 링크를 확인해주세요 (참고로 해당 소스는 java로 되어있습니다.)

https://github.com/devetude/BO...

ps) 동문이시네요...?

cache[0] = 0;
cache[1] = input[1];
cache[2] = input[1] + input[2];

int max = result[1];

if (max < cache[2]) {
    max = cache[2];
}

int i;

for (i = 3; i <= n; i++) {
    if (cache[i - 3] + arr[i - 1] + arr[i] >= cache[i - 2] + arr[i]) {
        cache[i] = cache[i - 3] + arr[i - 1] + arr[i];
    }
        
    else {
        cache[i] = cache[i - 2] + arr[i];
    }
        
    if (cache[i] < cache[i - 1]) {
        cache[i] = cache[i - 1];
    }
    
    if (max < cache[i]) {
        max = cache[i];
    }
}

printf("%d", max);

shw8581 7년 전 0

안녕하세요 깃허브에 들어가보니 저보다 선배이신거같네요. 저는 13학번 학생입니다 선배님께서 올려주신 소스코드에 도움받아 채점완료했습니다. 하나 더 배워가는거 같습니다 감사합니다 밑은 저의 소스코드입니다 앞으로도 가끔씩 피드백 부탁드려도 될까요?

#include<stdio.h>
int max(int a, int b) {
	return a >= b ? a : b;
}

int main(void){
	int num[10001] = {};
	int dp[10001] = {};
	int result;
	int tc;
	scanf("%d", &tc);

	for (int i = 1; i <= tc; i++) {
		scanf("%d", &num[i]);
		if (num[i] > 1000) {
			i--;
			continue;
		}
	}	
	dp[1] = num[1];
	dp[2] = num[1] + num[2];

	for (int k = 3; k <= tc; k++) {
		dp[k] = max(num[k] + num[k - 1] + dp[k - 3], num[k] + dp[k - 2]);
		dp[k] = max(dp[k], dp[k - 1]);
	}
	printf("%d\n", dp[tc]);
}

devetude 7년 전 0

네 ^^; 실력은 짧지만 언제든 도움을 드릴 수 있다면 답변을 해드리겠습니다.

남은 방학 알차고 건강하게 보내세요!

shw8581 7년 전 0

네 감사합니다 선배님도 남은방학 알차게 보내시구요 그나저나 백준에서 피드백요청할려면 따로 메시지같은기능이 있나요?

devetude 7년 전 0

음... 메세지 기능은 없는걸로 알고있습니다.

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

문제

문제

출처

ICPC

계단오르기와 동일한 dp적용후 저

shw8581 7년 전 0

devetude 7년 전 0

shw8581 7년 전 0

devetude 7년 전 0

shw8581 7년 전 0

devetude 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말