[C] 백준 - 1912번: 연속합

3월 9일(목) - 동적계획법 1 (1912번)

1912번: 연속합

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 순서대로 n개의 수를 입력받는 과정에서 0보다 크냐 아니면 0보다 작냐를 기준으로 계산을 나누어야한다고 생각

- 입력받은 수가 0보다 크면,  중간과정의 합을 넣어놓을 dp 배열에 그대로 더해서 넣는다

- 입력받은 수가 0보다 작으면, 다시 if - else로 나누어서 중간과정의 합을 0으로 초기화할 것 인지 아닌지를 판단한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 아래의 풀이처럼 코드를 작성했더니 3개의 예제 모두 잘못된 출력값이 나옴

-> 풀이가 꼬인 것 같아서 처음부터 다시 시작

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

	int num[100001];
	int dp[100001];
	int sum = 0;

	for (int i = 1; i < n + 1; i++)
	{
		scanf("%d", &num[i]);
	}
	
	dp[0] = num[0];
	for (int i = 1; i < n; i++)
	{
		sum = sum + num[i];
		if (num[i] > 0)
		{
			dp[i] = dp[i - 1] + num[i];
		}
		else
		{
			if (dp[i - 1] > dp[i - 1] + num[i])
			{

			}
			else
			{
				dp[i] = dp[i - 1] + num[i];
			}
		}
	}

	if (sum < dp[n-1])
	{
		printf("%d", dp[n - 1]);
	}
	else
	{
		printf("%d", sum);
	}

	return 0;
}

 

2.

-> 인덱스값과 순서가 달라서 혼동이 생기는 반복문을 0부터 n-1이 아니라 1부터 n까지로 변경

     dp배열도 직관적으로 tmp_sum으로 변경

-> 가장 먼저, 입력받은 수가 +인지 아니면 -인지를 토대로 추후 계산을 나누는 분기점을 삭제

-> 1) tmp_sum의 내용을 채우는 첫 번째 반복문을 2부터 n까지 돌린다

    단, tmp_sum[1]에는 가장 첫번째 숫자인 num[1] 값을 바로 넣은뒤 이후 계산을 진행한다

    2) 채워놓은 tmp_sum의 내용과 max 값을 비교하며 최종적으로 출력할 max 값을 탐색하는

    두번째 반복문은 1부터 n까지 돌린다

    이렇게 2가지의 반복문을 큰 틀로 잡기로 결정 

-> 첫 번째 반복문에서는 예제 1번처럼, 이전까지의 숫자들의 합을 버리고 새롭게 tmp_sum값을 선언해야하는 경우를

    if로 뽑아내기로 결정 그리고 else 에서는 평범하게 새롭게 입력된 num[ i ] 값을 tmp_sum[ i - 1 ]에 더한다

-> 두 번째 반복문에서는 max 값과 tmp_sum을 하나하나 비교하며, 최종적으로 출력할 max 값을 탐색

 

3. max 값을 0으로 설정했더니 예제 1번과 2번은 문제없지만, 예제 3번에서는 출력값이 0으로 나옴

-> max 값을 -1000 x 1000으로 바꾸어서 선언

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int num[100001];
	int tmp_sum[100001];

	int n;
	scanf("%d", &n);

	for (int i = 1; i < n + 1; i++)
	{
		scanf("%d", &num[i]);
	}

	tmp_sum[1] = num[1];
	for (int i = 2; i < n + 1; i++)
	{
		if (tmp_sum[i - 1] + num[i] < num[i])
		{
			tmp_sum[i] = num[i];
		}
		else
		{
			tmp_sum[i] = tmp_sum[i - 1] + num[i];
		}
	}

	int max = -1000000;
	for (int i = 1; i < n + 1; i++)
	{
		if (max < tmp_sum[i])
		{
			max = tmp_sum[i];
		}
	}

	printf("%d", max);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ