[BOJ 20500] Ezreal 여눈부터 가네 ㅈㅈ

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

20500번: Ezreal 여눈부터 가네 ㅈㅈ

 

- 문제 요약

 

N자리 양의 정수 중에서 15의 배수의 개수를 구하시오.

이때, 문제의 답은 1000000007로 나눈 나머지를 출력하시오.

(1<=N<=1515)

 

 

- 알고리즘 정리

 

15의 배수는 3과 5의 공배수입니다.

그러면 15의 공배수는 끝자리가 5 또는 10, 각 자릿수의 합이 3의 배수여야 성립됩니다.

 

이 문제는 DP로 풀면 좋을 것 같네요.

 

n의 범위가 1515니까 dp 배열의 크기는 넉넉잡아 1520으로 만들겠습니다.

그리고 dp 배열의 의미는 아래와 같이 정의하겠습니다.

 

dp[i] : i자리 양의 정수 중 15의 배수의 개수

우선 Tast Case 1, 2, 3에서 dp[1], dp[2], dp[3]을 주었습니다.

dp[1]=0, dp[2]=1, dp[3]=1

 

그런데, 이것만 봐서는 점화식을 어떻게 만들어야 할지 감이 오지 않으니 그냥 노가다로 조금 더 구해봤습니다.

dp[4]=3, dp[5]=5, dp[6]=11

 

dp 배열에서 규칙이 보이는 것 같습니다.

이제 점화식을 만들어보겠습니다.

 

우선, n이 짝수인지 홀수인지에 따라 점화식이 달라집니다.

 

n이 짝수 : dp[i]=dp[i-1]*2+1

n이 홀수 : dp[i]=dp[i-1]*2-1

 

문제에서 답을 출력할 때 1000000007로 나누어 출력하라고 했으니, 값이 넘치는 걸 방지하기 위해 dp[i]에 값을 저장할 때마다 1000000007로 나누어 저장하겠습니다.

그러면 최종 점화식은 아래와 같이 나오게 됩니다.

 

n이 짝수 : dp[i]=(dp[i-1]*2+1)%1000000007

n이 홀수 : dp[i]=(dp[i-1]*2-1)%1000000007

 

 

- 코드 작성

 

dp[i]에 값을 저장할 때마다 1000000007로 나누어 저장하긴 했지만, 그래도 long long 타입으로 만들어놓는 게 마음이 편하기 때문에 dp 배열은 long long 타입으로 선언하겠습니다.

 

#include<cstdio>
#include<iostream>
using namespace std;

typedef long long ll;
ll dp[1520],n,arr[1520];

int main(){
	cin>>n;
	dp[1]=0,dp[2]=1,dp[3]=1,dp[4]=3,dp[5]=5,dp[6]=11;
	if(n<=6){
		cout<<dp[n];
		return 0;
	}
	for(int i=7;i<=n;i++){
		if(i%2==0){
			dp[i]=(dp[i-1]*2+1)%1000000007;
		}
		else{
			dp[i]=(dp[i-1]*2-1)%1000000007;
		}
	}
	cout<<dp[n];
	return 0;
}

코드 제출 결과

dp 문제는 역시 손으로 노가다를 조금이라도 한 다음에 푸는게 정신건강에 좋은 것 같습니다.

노가다 없이 그냥 풀면 정신 나갈 것 같네요.