[C] 백준 - 2629번: 양팔저울

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

2629번: 양팔저울

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

 

최초 생각 정리

- dp를 활용한 방식의 풀이를 예상 + 아마 냅색 알고리즘으로 2차원 dp ...?

 

- 입력은 추의 개수 / 추의 무게들 / 구슬의 개수 / 구슬들의 무게가 주어지므로

  num_of_weight / weight[ 31 ] / num_of_bead / bead[ 8 ] 로 각각 입력받는다

- dp[ 추의 순서 ][ 목표 무게 ]로 설정하며, 

  1) dp[ i+1 ][ w ]

      새로운 추를 올리지 않는 경우

  2) dp[ i+1 ][ w + weight[i] ]

      새로운 추를 기존 추가 존재하던 저울에 올리는 경우

  3) dp[ i+1 ][ w - weight[i] ]

      새로운 추를 구슬 쪽에 올리는 경우로 나누어서 구현한다

- 출력은 dp[ ][ ]값이 1이면 Y를, 이외에는 N을 출력한다

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

 

문제점

1. 구슬들의 무게를 굳이 bead[ 8 ]에 저장해서 받을 필요가 없음

-> num_of_bead만큼 for문을 돌리는 과정에서 변수 bead 값을 scanf로 받는것으로 수정

 

2. 새로운 추를 구슬 쪽에 올리는 경우에는 w - weight[ i ]값이 음수가 될 수 있다는 것을 뒤늦게 확인

-> abs 함수 추가

 

3. 최종풀이의 solve 함수에 해당하는 내용은 이미 작성했지만, main함수에서 한번에 처리하려다가 오류 발생

-> 아래의 풀이를 참고하여 solve 함수로 따로 빼고,

-> 기존 풀이에서 dp[ ][ ]를 갱신하던 것을, solve 함수에 대한 재귀호출로 수정

[C/C++] 백준 2629번 - 양팔저울 (DP풀이)

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

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <math.h>

int num_of_weight;
int weight[31];
int dp[31][40001];

void solve(int i, int w)
{
	if (i > num_of_weight || dp[i][w] == 1)
	{
		return;
	}

	dp[i][w] = 1;
	solve(i + 1, w);
	solve(i + 1, w + weight[i]);
	solve(i + 1, abs(w - weight[i]));
}

int main(void)
{	
	scanf("%d", &num_of_weight);
	for (int i = 0; i < num_of_weight; i++)
	{
		scanf("%d", &weight[i]);
	}

	solve(0, 0);

	int num_of_bead;
	scanf("%d", &num_of_bead);
	for (int i = 0; i < num_of_bead; i++)
	{
		int bead;
		scanf("%d", &bead);

		if (bead > 15000)
		{
			printf("N ");
		}
		else if (dp[num_of_weight][bead] == 1)
		{
			printf("Y ");
		}
		else
		{
			printf("N ");
		}
	}

	return 0;
}

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