[백준] 5557 1학년

참고: https://www.acmicpc.net/problem/5557

5557번: 1학년

---

주어진 수들의 연산(+, -) 결과가 배열의 마지막 수가 되는 경우의 수를 구하는 문제입니다.

 

일단 문제에서 주어진 단서들을 나열합니다.

 

수의 범위는 0이상 20이하이고, 배열의 크기는 3이상 100 이하 입니다. 그리고 올바른 등식의 개수의 범위가 2^63 - 1까지 입니다.

 

여기서 얻을 수 있는 힌트는 배열의 크기가 그리 크지 않으므로 이중 for문 정도는 사용할 수 있고, 정답을 저장할 변수 타입은 자바라면 long이 적당할 것 같습니다.

 

그리고 주어진 배열 arr이 [8 3 2 4 8 7 2 4 0 8 8] 라고 가정합니다. 

arr[0] + arr[1] = 11, arr[0] - arr[1] = 5 

11 + arr[2] = 13, 11 - arr[2] == 9 ....

 

연산을 할 때 마다 그 개수가 2^N 만큼 커집니다. 매우 많은 수가 나올 수 있다는 것이고, 그렇다는 것은 동일한 결과가 나올 경우도 존재한다는 것입니다.

 

다시 말하자면, 7 - 2, 8 - 3, 9 - 4, 11 - 6 의 연산 결과가 모두 5로 동일하기 때문에 굳이 하나씩 저장할 필요 없이, 나타난 결과의 카운트만 저장하고, 다음에 5 와 어떤 수의 연산 결과 A가 나올 경우 A가 나오는 카운트를 5가 나온 카운트 만큼만 더해주자는 것 입니다. 결론적으로 이 문제는 중복된 하위 문제들로 이루어져 다이나믹 프로그래밍으로 풀 수 있습니다.

 

이제는 고민할 것 없이 다이나믹 프로그래밍으로 코드를 작성하되, 연산의 결과가 0이상 20 이하인 것만 신경써주면 됩니다.

 

시간 복잡도는 굳이 말하자면 O(20 * N) 이니 O(N) 시간에 해결할 수 있습니다.

 

Python

	from sys import stdin
	import collections
	readline = stdin.readline
	N = int(readline())
	arr = list(map(int, readline().split()))
	def solve():
	dp = collections.defaultdict(int)
	dp[arr[0]] = 1
	for index in range(1, N-1):
	new_dp = collections.defaultdict(int)
	for current in dp:
	n1, n2 = current + arr[index], current - arr[index]
	if 0 <= n1 <= 20:
	new_dp[n1] += dp[current]
	if 0 <= n2 <= 20:
	new_dp[n2] += dp[current]
	dp = new_dp
	print(dp[arr[-1]])
	solve()

view raw BOJ5557.py hosted with ❤ by GitHub

Java

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class BOJ5557 {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int N = Integer.parseInt(st.nextToken());
	int[] arr = new int[N];
	st = new StringTokenizer(br.readLine(), " ");
	for (int i=0;i<N;i++){
	arr[i] = Integer.parseInt(st.nextToken());
	}
	long[] dp = new long[21];
	dp[arr[0]] = 1;
	for(int i=1;i<N-1;i++) {
	long[] temp = new long[21];
	for (int j=0;j<=20;j++) {
	if (dp[j] == 0) continue;
	int n1 = j + arr[i], n2 = j - arr[i];
	if (n1 >= 0 && n1 <= 20)
	temp[n1] += dp[j];
	if (n2 >= 0 && n2 <= 20)
	temp[n2] += dp[j];
	}
	dp = temp;
	}
	System.out.println(dp[arr[N-1]]);
	}
	}

view raw BOJ5557.java hosted with ❤ by GitHub