[C] 백준 - 7579번: 앱

8월 7일(월) - 다이나믹 프로그래밍 (7579번)

7579번: 앱

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

 

최초 생각 정리

- 이전에 풀이했던 "12865번: 평범한 배낭" 문제의 풀이와 비슷한 방향의 풀이를 예상

 

- 입력은 N과 M, 그리고 N개의 메모리바이트수는 memory배열에, N개의 비활성화 비용은 cost배열에 입력받는다

  이때, cost의 누적합을 변수 sum에 저장한다

- 이중 for문 안에서 dp[ i ][ j ] 값을 12865번 풀이와 비슷한 방식으로 갱신해준다

- 출력은 sum의 숫자만큼 for문을 돌리면서 dp[ N ][ i ]값이 M보다 크거나 같은 경우의 i를 출력한다

[C] 백준 - 12865번: 평범한 배낭

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

 

문제점

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

 

풀이 -> 틀렸습니다 (2023.11.19 재채점)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#define MAX(x, y) (((x) > (y)) ? (x) : (y))

#include <stdio.h>

int memory[101];
int cost[101];
int dp[101][10001];

int main(void)
{
	int N, M;
	int sum = 0;
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &memory[i]);
	}
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &cost[i]);
		sum = sum + cost[i];
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= sum; j++)
		{
			if (j - cost[i] >= 0)
			{
				dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	for (int i = 0; i <= sum; i++)
	{
		if (dp[N][i] >= M)
		{
			printf("%d", i);
			break;
		}
	}

	return 0;
}

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

 

수정 풀이 (2023.12.18)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#define MAX(x, y) (((x) > (y)) ? (x) : (y))

#include <stdio.h>

int memory[101];
int cost[101];
int dp[101][10001];

int main(void)
{
	int N, M;
	int sum = 0;
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &memory[i]);
	}
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &cost[i]);
		sum = sum + cost[i];
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= sum; j++) // int j = 1 로 시작하던 풀이를 int j = 0으로 수정
		{
			if (j - cost[i] >= 0)
			{
				dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	for (int i = 0; i <= sum; i++)
	{
		if (dp[N][i] >= M)
		{
			printf("%d", i);
			break;
		}
	}

	return 0;
}

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