(백준 2293번 동전 1) 라이님 블로그 대회 알고리즘 따라잡기 14) 투 포인터, 슬라이딩 윈도우

슬라이딩 윈도우로 풀어본 문제!

 

아이디어는 매우 단순한데, 푸는데는 시간이 조금 걸렸다^___^

 

백준 2293번 

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

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
using namespace std;

int pos[10001];

int main() {
	int n, k; scanf("%d %d", &n, &k);
	memset(pos, 0, sizeof(pos));

	for (int i = 0; i < n; i++) {
		int temp; scanf("%d", &temp);
		// ★ 원하는 합보다 더 큰 동전이 들어올 가능성 有
		if(temp > k) continue;
		pos[temp]++;
		for (int j = 1; j < k + 1; j++) {
			if (j >= temp) pos[j] += pos[j - temp];
		}
	}
	printf("%d", pos[k]);
}

 

https://www.acmicpc.net/board/view/27103

동전의 가치가 10,000보다 클 수도 있다^0^

 

놀랍게도 그런 경우가 존재하기 때문에 예외 처리를 해줘야 한다.

이걸 안해줘서 런타임에러로 20분간 고통받았다...