백준] 2193 : 이친수

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

2193번: 이친수

 

문제  : 

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

 

 

입력  : 

첫째 줄에 N이 주어진다.

 

 

출력  : 

첫째 줄에 N자리 이친수의 개수를 출력한다.

 

 

 

 

접근 방법

 

처음 생각해본 접근 방법

일단 가장 중점적인 것은
0으로 시작하지 않는 것. 1이 두 번 연속이 아닌 것. 이 두 가지다.

처음 int dp는 int dp[91][2]로 초기화.

예제 1번을 참고하자.
3을 입력했을 때, 2가 출력된다.
그렇다면 결과는 두 가지. 101, 100.

dp[3][i]를 2로 초기화해준다.
(이런식으로 입력 1일 때와 2일 때도 초기화할 수 있을 것 같다.)

생각할 수 있는 경우의 수는.
0으로 끝났을 때, 0과 1로 끝날 수 있고.
1로 끝났을 때는 0만 가능하다.
따라서 각각 dp[N][i] = dp[N][i + 2]  && dp[N - 1][i] = dp[N - 1][i + 1]

만약 4 입력이면 1000, 1001, 1010로 3출력
5입력이면 10000, 10101, 10100, 10010, 10001.

처음 짜본 코드

#include <iostream>
using namespace std;

int dp[91][2];
int N, sum;

int main(){

	cin >> N;
	
	dp[1][1] = 1;
	for(int i = 0; i < 2; i++){
		if(i == 0){
			dp[2][i] = 1;
			
		}
		dp[3][i] = 1;
	}
	
	for(int i = 3; i <= N; i++){
		for(int j = 0; j < 2; j++){
			if(j == 0){
				dp[i][j] = dp[i - 1][j + 2];
			}else if(j == 1){
				dp[i][j] = dp[i - 1][j + 1];
			}
		}
	}
	
	for(int i = 0; i < 2; i++){
		sum += dp[N][i];
	}
	
	cout << sum;
	return 0;
}

 

두 번째 수정된 코드

#include <iostream>
using namespace std;

int dp[91][2];
int N, sum;

int main() {

	cin >> N;
	
	dp[1][1] = 1;
	for(int i = 0; i < 2; i++){
		if(i == 0){
			dp[2][i] = 1;
			
		}
		dp[3][i] = 1;
	}
	
	for(int i = 3; i <= N; i++){
		for(int j = 0; j < 2; j++){
			if(j == 0){
			//	dp[i][j] = dp[i - 1][j + 2];
				dp[i][j] = dp[i - 1][j] + 1;

			}else if(j == 1){
			//	dp[i][j] = dp[i - 1][j + 1];
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	
	for(int i = 0; i < 2; i++){
		sum += dp[N][i];
	}
	
	cout << sum;
	
	return 0;
}

 

 

 

** 다른 분들이 짠 코드를 본 결과,

 

1) 1차원 배열로 짜도 된다. & 2차원으로도 가능.

2) 이중 for문을 돌리지 않아도 된다.

3) 점화식을 다시 세워보자.

 

 

 

 

정답 코드

#include <iostream>
using namespace std;

long long dp[91]; // int가 아니라 long long으로 선언해야 저장 가능한 크기를 초과하지 않는다.
int N;

int main() {

	cin >> N;
	
	dp[1] = 1;
	dp[2] = 1;
	dp[3] = 2;
    
	for(int i = 4; i <= N; i++){
		dp[i] = dp[i - 1] + dp[i - 2];
	}
		
	
	cout << dp[N];
	
	return 0;
}

#include <iostream>
using namespace std;

long long dp[91][2];
int N;

int main() {

	cin >> N;
	
	dp[1][0] = 0; // 11이면 체크 X
	dp[1][1] = 1;

	
	for(int i = 2; i <= N; i++){
				dp[i][0] = dp[i - 1][0] + dp[i - 1][1]; // 0이 오면 1과 0이 올 수 있고,
				dp[i][1] = dp[i - 1][0]; // 1이 오면 0만 올 수 있음
	}
	
	cout << dp[N][1] + dp[N][0];
	
	return 0;
}

 

 

 

[알고리즘] 백준 이친수 2193 DP

[백준][2193번][DP] 이친수

백준 2193번 : 이친수

[백준] 2193: 이친수