[백준] 13902 개업 2, python(pypy), C++

https://www.acmicpc.net/problem/13902

13902번: 개업 2

문제 자체는 어렵진 않으나 시간초과의 벽이 조금 있었다.

이 문제를 풀기위해서 동적계획법을 사용해야한다. 

최대 두개의 웍을 사용해서 처리할 수 있는 양을 구해야하는데 set이라는 자료구조를 사용했다.

 

두개로 처리할수 있는 양을 동적 계획하여 0부터 N번째 양까지 계산하면 된다.

import sys; input = sys.stdin.readline
N, M = map(int, input().split())
wok = list(map(int, input().split()))
wok_set = set(wok)
for i in range(M):
    for j in range(i + 1, M):
        wok_set.add(wok[i] + wok[j])
INF = 1234567890
memo = [INF for _ in range(10001)]
memo[0] = 0
for i in range(N):
    for k in wok_set:
        if i + k > 10000: continue
        memo[i + k] = min(memo[i] + 1, memo[i + k])

if INF == memo[N]:
    print(-1)
else:
    print(memo[N])

 

C++에선 set이라는 자료구조가 있지만 똑같이 하려니 시간초과가 되었다.

set대신 배열을 사용해서 amount를 체크했다.(true값일 때 해당량을 처리할수 있다)

#include<iostream>
#include<algorithm> // fill
using namespace std;
#define INF 987654321
#define min(x, y) (x > y) ? y : x
int memo[10001];
int wok[1000];
bool amount[10001];

int main() {
	// 0 입력
	int N, M, i, j, k;
	cin >> N >> M;
	for (i = 0; i < M; i++)
		cin >> wok[i];

	// 1 하나 또는 두개의 웍을 사용해서 만들수 있는 요리의 양 계산
	for (i = 0; i < M; i++)
	{
		amount[wok[i]] = true;
		for (j = i + 1; j < M; j++) {
			if (wok[i] + wok[j] > N) continue;
			amount[wok[i] + wok[j]] = true;
		}
	}
	// 2 dp계산
	fill(memo, (memo + N + 1), INF);
	memo[0] = 0;
	for (i = 0; i <= N; i++)
		if (amount[i]) memo[i] = 1;
	for (i = 0; i <= N; i++)
	{
		for (k = 0; k <= N; k++)
		{
			if (!amount[k]) continue;
			if (i + k > N) continue;
			memo[i + k] = min(memo[i] + 1, memo[i + k]);
		}
	}
	// 3 출력
	if (memo[N] == INF)
		cout << -1 << '\n';
	else
		cout << memo[N] << '\n';
	return 0;
}

파이썬에서 사용한 알고리즘보다는 빨라졌지만 이 방법도 불필요한 연산이 많다.

하지만... 시간이 너무 소요되었으므로 여기서 그만두도록 하겠다.