BOJ 2193 : 이친수 -C++
이친수
- 해당 문제는 결과적으로 피보나치 점화식으로 풀리긴 한다.
하지만, 이것은 해당 문제의 본질을 파악한 것은 아님
- key point! (본질을 파악한 풀이)
1) 해당 자리수에서 끝이 0으로 끝나는 요소는 0과 1이 붙을 수 있다
ex) 100
-> 101
/ 100
2) 해당 자리수에서 끝이 1로 끝나는 요소는 0만 붙을 수 있다
ex) 101
-> 100
코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
// d[i][1] = i 자리수 일 때 끝이 1인 개수
// d[i][0] = i 자리수 일 때 끝이 0인 개수
long long d[92][2];
int N;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
d[1][1] = 1;
d[2][0] = 1;
d[3][0] = 1; d[3][1] = 1;
for(int i=4;i<=N;i++)
{
d[i][0] = d[i-1][0] + d[i-1][1];
d[i][1] = d[i-1][0];
}
cout << d[N][0] + d[N][1];
return 0;
}
- 테이블 정의
D[i][0] = i 자리수 2진수 중 0으로 끝나는 요소의 개수
D[i][1] = i 자리수 2진수 중 1으로 끝나는 요소의 개수
- 점화식
D[i][0] = D[i-1][0] + D[i-1][1]
D[i][1] = D[i-1][0]
- 점화식 이해하기
ex)
i
가 4일 경우 1000
/ 1010
/ 1001
이렇게 3가지 가 나오는데,
끝이 0인 요소는 뒤에 0과 1을 추가할 수 있으며,
끝이 1인 요소는 뒤에 0만 추가해야한다.
즉, 1000
-> 10000
/ 10001
1010
-> 10100
/ 10101
1001
-> 10010
이 된다!
결과적으로,
D[5][0]
은 D[4][0] + D[4][1]
(끝이 0이 되는 것 = 전 자리수의 0요소 개수 + 전 자리수 1의 개수)
D[5][1]
은 D[4][0]
(끝이 1이 되는 것 = 전 자리수의 0요소 개수)
Author And Source
이 문제에 관하여(BOJ 2193 : 이친수 -C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-2193-이친수-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 해당 문제는 결과적으로 피보나치 점화식으로 풀리긴 한다.
하지만, 이것은 해당 문제의 본질을 파악한 것은 아님
- key point! (본질을 파악한 풀이)
1) 해당 자리수에서 끝이 0으로 끝나는 요소는 0과 1이 붙을 수 있다
ex)100
->101
/100
2) 해당 자리수에서 끝이 1로 끝나는 요소는 0만 붙을 수 있다
ex)101
->100
#include <string> #include <vector> #include <iostream> using namespace std; // d[i][1] = i 자리수 일 때 끝이 1인 개수 // d[i][0] = i 자리수 일 때 끝이 0인 개수 long long d[92][2]; int N; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N; d[1][1] = 1; d[2][0] = 1; d[3][0] = 1; d[3][1] = 1; for(int i=4;i<=N;i++) { d[i][0] = d[i-1][0] + d[i-1][1]; d[i][1] = d[i-1][0]; } cout << d[N][0] + d[N][1]; return 0; }
- 테이블 정의
D[i][0] = i 자리수 2진수 중 0으로 끝나는 요소의 개수
D[i][1] = i 자리수 2진수 중 1으로 끝나는 요소의 개수
- 점화식
D[i][0] = D[i-1][0] + D[i-1][1]
D[i][1] = D[i-1][0]
- 점화식 이해하기
ex)
i
가 4일 경우1000
/1010
/1001
이렇게 3가지 가 나오는데,
끝이 0인 요소는 뒤에 0과 1을 추가할 수 있으며,
끝이 1인 요소는 뒤에 0만 추가해야한다.
즉,1000
->10000
/10001
1010
->10100
/10101
1001
->10010
이 된다!
결과적으로,
D[5][0]
은D[4][0] + D[4][1]
(끝이 0이 되는 것 = 전 자리수의 0요소 개수 + 전 자리수 1의 개수)
D[5][1]
은D[4][0]
(끝이 1이 되는 것 = 전 자리수의 0요소 개수)
Author And Source
이 문제에 관하여(BOJ 2193 : 이친수 -C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-2193-이친수-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)