[백준 - Python] 2193 - 이친수

0.  문제 링크

 

 

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

2193번: 이친수

---

1.  풀이 방법

 

 

1. 0으로 끝나는 숫자와 1로 끝나는 숫자를 구분한다.
2. i 자리의 숫자는 i - 1 번째 어떤 숫자든 0을 붙여도 상관없다.
3. i 자리의 숫자는 i - 1 번째 숫자에서 끝이 0으로 끝나는 숫자에만 1을 붙일 수 있다.
4. 이런 점화식을 세운 후 문제를 풀면 끝

 

• 조금 더 최적화를 위해서 메모리를 2*2만 사용하였다.
• 실제 메모리 사용은 줄어들지 않았는데, 이유는 잘 모르겠다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline


def logic():
    i = False
    for _ in range(2, n + 1):
        maps[i][0] = maps[i - 1][0] + maps[i - 1][1]        # 0으로 끝나는 거
        maps[i][1] = maps[i - 1][0]

        i = not i


if __name__ == "__main__":
    n = int(input())

    maps = [[0] * 2 for _ in range(2)]
    maps[1][0] = 0      # 한 자리 수가 0으로 끝나는 것
    maps[1][1] = 1      # 한 자리 수가 1로 끝나는 것

    logic()

    print(maps[n % 2][0] + maps[n % 2][1])

---

3.  마무리

 

 

2년 전에 푼 경험이 있길래 풀어봤는데, 시간이 확실히 줄어들었다.

메모리는 3000KB 더 쓰기는 했는데 뭐 그래봤자 3MB니까 뭐....

이번에는 DP로 풀었는데, 2년 전에는 피보나치 수열로 풀었었음

 

8분 정도 풀었는데, 확실히 성장했다는게 느껴져서 기분이 좋았다.