[백준(BOJ)] 2193번 : 이친수 - C++[CPP]

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

2193번: 이친수

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

---

 

⊙ 문제 접근 과정

 

이친수는 첫 번째 숫자가 1이고, 1이 연속해서 2번 오면 안 된다.

 

dp[0] = 0, dp[1] = 1, dp[2] = 1이다.

 

dp[1]은 하나, "0, 1" (첫번째 숫자 1 and 1이 연속해서 2번 안 옴)

dp[2]도 하나, "00, 01, 11, 10"

 

그렇다면 dp[3]은? "100, 101" 2개이다.

 

dp[4]는 "1000, 1001, 1010" 3개

dp[5]는 5개, dp[6]은 8, dp[7] = 13이고 dp[8] = 21이다.

 

표로 정리해보면

dp[0]	0
dp[1]	1
dp[2]	1
dp[3]	2
dp[4]	3
dp[5]	5
dp[6]	8
dp[7]	13
dp[8]	21

dp[i] = dp[i-1] + dp[i-2] 규칙이 보인다.

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <string>
#include <algorithm> //reverse 함수가 있는 헤더파일

using namespace std;


int main() {
	string N;
	
    //0이 아니면 무한 반복
    while (N!="0") {
        cin >> N;
        string buf =N;
        reverse(N.begin(), N.end()); // 앞 뒤 바꿈
        if (N=="0") { // 즉시 탈출 (왜냐하면 0도 reverse하면 0으로 같다.)
            break;
        }
        else if(N == buf) { // 비교
            cout <<"yes\n";
        }else {
            cout <<"no\n";
        }
    }  
}

---

⊙ 결과

 

---

 

 

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!