AOJ - Problem 1105 : Unable Count

• 問題文

[1,n]のうちa*i+b*jで表せない数が何個あるか数える問題です。入力a,b,nは10^6以下の整数でi,jは非負整数です。

動的計画法で解ける問題でした。dp[x] := 整数xをa*i+b*jで表すことができるかどうか(0 or 1)で計算しました。dp[0]を1で初期化し、iを0からnまでループしてdp[i]が1だったときはdp[i+a]とdp[i+b]を1にするようにしていきました。

#include <iostream>
using namespace std;

int main(){
	int n,a,b;
	while( cin >> n >> a >> b , n || a || b ){
		int dp[1000001] = {0};
		dp[0] = 1;
		for(int i=0 ; i <= n ; i++ ){
			if( dp[i] == 1 ){
				if( i+a <= n ){
					dp[i+a] = 1;
				}
				if( i+b <= n ){
					dp[i+b] = 1;
				}
			}
		}
		int ans = 0;
		for(int i=1 ; i <= n ; i++ ){
			if( dp[i] == 0 ){
				ans++;
			}
		}
		cout << ans << endl;
	}
}