일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- DataBinding Error
- 알고리즘
- 코틀린
- clean architecture
- 빅데이터청년인재
- kotiln
- IT연합동아리
- flownet
- NEXTERS
- 데이터청년캠퍼스
- utuntu
- 인공지능
- 딥러닝
- Android
- sending 404
- 이것만보면돼
- 안드로이드
- 백준
- 넥스터즈
- 머신러닝
- nvcc
- ubuntu
- ubuntu18.04
- resample2d_cuda
- cuda-10.2
- 소켓통신
- 청년인재
- 빅데이터
- 자바
- 빅데이터청년캠퍼스
- Today
- Total
보초의 코딩일기장
백준 15990번: 1, 2, 3 더하기 5 본문
문제)
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
1+2+1
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력)
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
예제 입력)
3 4 7 10
4의 경우, 1+2+1, 1+3, 3+1 => 3가지
n=4일 때,
x+1 = n이 되는 경우 1앞에 올 수 있는 수는 2 또는 3 (연속으로 수가 올 수 없으므로 1은 제외함)
x+2 = n, 2 앞에 올 수 있는 수는 1 또는 3
x+3 = n, 3 앞에 올 수 있는 수는 1 또는 2
점화식으로 나타낸다면,
D[n][1]=D[n-1][2]+D[n-1][3]; //n을 만들기 위한 경우의 수 중, 마지막 피연산자가 1인 경우의 수
D[n][2]=D[n-2][1]+D[n-2][3];
D[n][3]=D[n-2][2]+D[n-3][1];
로 나타낼 수 있다.
단 n=0, 1, 2, 3일 때의 예외처리를 해주어야 한다.
1. 0을 만들 수 있는 경우의 수는 0개.
2. 1의 경우의 수는 마지막 피연산자가 1인 경우,
3. 2의 경우의 수는 마지막 피연산자가 2인 경우,
4. 3의 경우의 수는 마지막 피연산자가 1,2,3인 경우일 때 각각1가지씩 존재한다.
1.
D[0][1]=0;
D[0][2]=0;
D[0][3]=0;
2.
D[1][1]=1;
D[1][2]=0;
D[1][3]=0;
3.
D[2][1]=0;
D[2][2]=1;
D[2][3]=0;
4.
D[3][1]=1;
D[3][2]=1;
D[3][3]=1;
내가 짠 코드)
#include <iostream>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int d[100001][4];
int n;
int t;
cin>>t;
d[0][1]=0;
d[0][2]=0;
d[0][3]=0;
d[1][1]=1;
d[1][2]=0;
d[1][3]=0;
d[2][1]=0;
d[2][2]=1;
d[2][3]=0;
d[3][1]=1;
d[3][2]=1;
d[3][3]=1;
for(int i=4;i<=100000;i++){
d[i][1]=(d[i-1][2]+d[i-1][3])%1000000009;
d[i][2]=(d[i-2][1]+d[i-2][3])%1000000009;
d[i][3]=(d[i-3][1]+d[i-3][2])%1000000009;
}
while(t){
cin>>n;
cout<<(d[n][1]+d[n][2]+d[n][3])%1000000009<<'\n';
t--;
}
}
그런데!
int d[100001][4];
배열을 int로 선언해주니 큰 수를 입력할 때 오버플로우가 나타났다ㅠㅠ
반례인 경우로 99991 입력시
-42247586 |
라는 결과값이 나왔기 때문에
long long d[100001][4];
int -> long long 으로 변경해주었더니 맞았다 !
'일상' 카테고리의 다른 글
Ubuntu 18.04 Error) sudo: unknown uid 1000: who are you? (0) | 2020.01.08 |
---|---|
백준 10844번: 쉬운 계단 수 (0) | 2020.01.07 |
Baekjoon 16194번: 카드 구매하기2 (0) | 2020.01.07 |
Baekjoon 11052번: 카드 구매하기 (0) | 2020.01.07 |
넥스터즈(NEXTERS) 16기 개발자 지원, 면접 후기 (1) | 2020.01.07 |