문제

풀이

Coin Change라는 이름으로 유명한 DP 문제이다. 이 문제는 2차원 배열을 사용해서 해결할수도 있고 1차원 배열을 사용해서 해결할수도 있는데 2차원 배열 사용하면 6MB 정도의 메모리를 사용하게 되므로 문제의 메모리 제한을 초과하게 된다. 

일단 2차원 풀이법부터 설명해보자면, dp[n][k] = n 종류의 동전으로 k원을 만드는 경우의 수라고 정의할때 dp[n][k]를 구하는 방법은 두가지이다.

1. dp[n][k-coin[n]] = n번째 동전을 사용한 뒤 k원을 만들수 있는 경우의 수

2. dp[n-1][k] = n번째 동전을 사용하지 않고 k원을 만들수 있는 경우의 수

이렇게 되므로 점화식은 $ dp[n][k] = dp[n][k-coin[n]] + dp[n-1][k] $가 된다.

#include<stdio.h>
#include<string.h>
int coin[100]={0},cache[100][10001];
int solve(int n,int k){
	if(n<0||k<0)return 0;
	if(k==0) return 1;
	if(cache[n][k] != -1) return cache[n][k];
	return cache[n][k] = solve(n,k-coin[n]) + solve(n-1,k);
	
}
int main() {
	int n,k,i;
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++){
		memset(cache[i],-1,sizeof(cache[i]));
		scanf("%d",&coin[i]);
	}
	printf("%d",solve(n-1,k));
}

물론 위는 2차원 배열을 사용해서 메모리 초과가 발생한다. 1차원 풀이는 아무리 생각해도 모르겠어서 여러 문서를 뒤져보고 이해했다.

2차원 배열을 사용하는 점화식이 $ dp[n][k] = dp[n][k-coin[n]] + dp[n-1][k] $인데, 여기서 n이 1증가하면 결국은 $ dp[n][k] = dp[n][k-coin[n]] $이되므로 $ \sum\limits_{i=coin[n]}^k cache[i] = cache[i] + cache[i - coin[n]] $이 된다.

#include <stdio.h>
int main(void) {
	int i,j,n,k,coin[100]={0},cache[10001]={0};
	scanf("%d%d",&n,&k);
	cache[0]=1;
	for(i=0;i<n;i++){
		scanf("%d",&coin[i]);
		for(j=coin[i];j<=k;j++)
			cache[j] += cache[j-coin[i]];
	}
	printf("%d",cache[k]);
	return 0;
}

문제

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

풀이

들어오는 이진수의 길이의 최대가 1000자리라고 했으니 십진수로 변환하면 최대 $2^{1001}-1$ 값이 들어온다는 의미이므로 long long을 이용하더라도 범위를 초과하므로 해결 할 수가 없다. 게다가 C언어에서는 직접 2진수 인풋을 받을 수 없으므로 문자열로 입력받아 처리하는게 제일 간편할것이다.

쉬프트 연산으로 17배는 $ x << 4 + x $ 이므로 똑같이 계산해주면 된다.

문자열이므로 가장 왼쪽(0번 인덱스)은 직접 계산을 하지않았는데 계산하지 않은 0번 인덱스는 항상 1~4 사이의 값이 나오므로 계산 후에 [0]의 문자가 무엇인지 보고 직접 출력하게 했다.

#include <iostream>
#include <string>
using namespace std;
int main() {
	int i=0,respos;
	string s,shifted,res,z="";
	cin>>s;
	res = shifted = s +"0000"; //왼쪽으로 << 4 연산;
	respos=res.size();
	for(i=s.size()-1;i>=0;i--){
		respos--;
		if(s[i]=='0')  continue;
		res[respos]++;
	}
	for(i=res.size()-1;i>0;i--){
		if(res[i]>='2'){
			res[i-1] += (res[i]-'0')/2;
			res[i] = ((res[i]-'0')%2)+'0';

		}
	}
	if(res[0]=='2') res[0]='0',cout<<"1";
	else if(res[0]=='3') res[0]='1',cout<<"1";
	else if(res[0]=='4') res[0]='0',cout<<"10";
	cout<<res;
}