글 읽기 - 맞았습니다!! 근데 제가 푼 방식이 DP가 맞는지 잘 모르곘습니다..

joony94 6년 전 0

우선 맞았습니다.

다만 제목처럼 제 풀이 방법이 DP의 원리와 같는지 궁금합니다.

세세히 말씀해주시면 감사합니다!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define min(a,b) a<b ? a : b

int N;
int **house;
int **sum;

void Init_() {
	int i, j, max;
	scanf("%d", &N);
	house = (int**)malloc(sizeof(int*)*N);
	sum = (int**)malloc(sizeof(int*)*N);
	for (i = 0; i < N; i++) {
		house[i] = (int*)malloc(sizeof(int) * 5);
		sum[i] = (int*)malloc(sizeof(int) * 3);
	}
	for (i = 0; i < N; i++) {
		for (j = 1; j <= 3; j++)
			scanf("%d", &house[i][j]);
	}
	max = house[0][1];
	for (i = 0; i < N; i++) {
		for (j = 1; j < 4; j++) {
			if (house[i][j] > max)
				max = house[i][j];
		}
	}

	for (i = 0; i < N; i++) {
		house[i][0] = max + 1;
		house[i][4] = max + 1;
	}
}

void solve_problem() {
	int i, j, M;

	for (i = 0; i <= 3; i++) {
		sum[0][i] = house[0][i+1];
	}

	for (i = 1; i < N; i++) {
		for (j = 0; j < 3; j++) {
			if (j == 0)
				M = min(sum[i - 1][1], sum[i - 1][2]);
			else if (j == 1)
				M = min(sum[i - 1][0], sum[i - 1][2]);
			else
				M = min(sum[i - 1][1], sum[i - 1][0]);
			sum[i][j] = M + house[i][j + 1];
		}
	}

	M = sum[N - 1][0];
	for (j = 0; j < 3; j++) {
		if (M > sum[N - 1][j])
			M = sum[N - 1][j];
	}
	printf("%d\n", M);
}

int main() {
	Init_();
	solve_problem();
}

ntopia 6년 전 1

그냥 DP네요. 잘 짜신 것 같은데요

joony94 6년 전 0

그렇군요! 감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

맞았습니다!! 근데 제가 푼 방식이 DP가 맞는지 잘 모르곘습니다..

joony94 6년 전 0

ntopia 6년 전 1

joony94 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말