[모각코] 210731 Today I Learned

210728 못 풀었던 문제 (타입 에러) https://amor-fati.tistory.com/39

[모각코] 210728 Today I Learned

 

N = int(input())
pinary = [0 for i in range(N)]

for i in range(N):
    if i == 0:
        pinary[i] = (0, 1)
    elif i == 1:
        pinary[i] = (1, 0)  # (0으로 끝나는 문자열 개수, 1로 끝나는 문자열 개수)
    else:
        pinary[i] = (pinary[i-1][0] + pinary[i-1][1], pinary[i-1][0])

print(pinary[-1][0] + pinary[-1][1])

for문을 돌 때 0번 자리에 있는 값(1 자릿수일 때 개수)은 굳이 필요 없을 것 같아서 1번부터 돌렸는데 그게 문제였다. 혹시 리스트 0번 값만 튜플 형태가 아니어서 그런가 싶어 0번부터 돌리는 for문으로 바꿨더니 바로 맞았습니다가 나왔다. 생각해보니 단지 형태가 달라서가 아니라, 1번부터 for문을 돌리면 input으로 1이 들어왔을 때 (1 자릿수 개수) 마지막 연산을 할 수 없기 때문에 타입 에러가 났던 것 같다. (1 자릿수 개수는 0번 인덱스 값에서 얻을 수 있는데 0번 값엔 튜플이 아닌 0이 들어가 있어서 마지막 연산을 할 수 없었다.) 어쨌든 해결 완료 ^________^

 

---

 

2011번: 암호코드 (acmicpc.net)

2011번: 암호코드

 

code = input()
case = [0 for i in range(len(code))]

for i in range(len(code)):
    if i == 0:
        if code[i] != '0':
            case[i] = (1, 0)    # (숫자 하나로 해석할 경우, 숫자 두 개로 해석할 경우)
        else:
            case[len(code)-1] = (0, 0)  # 코드 맨 앞자리가 0인 경우는 잘못된 코드 (해석할 수 있는 방법이 없음)
            break
    else:
        c = code[i-1] + code[i]
        if code[i] == '0':
            if c != '10' and c != '20': # 코드 중간에 0이 있을 경우, 앞자리가 1이나 2여서 같이 해석하는 방법만 있다
                case[len(code)-1] = (0, 0)
                break
            else:
                case[i] = (0, case[i-1][0])
        else:    
            if int(c) < 27:
                case[i] = (case[i-1][0] + case[i-1][1], case[i-1][0])
            else:
                case[i] = (case[i-1][0] + case[i-1][1], 0)

result = case[len(code)-1][0] + case[len(code)-1][1]
print(result%1000000)

 

숫자를 해석하는 방법은 크게 두 가지 경우가 있다. 숫자를 하나만 해석할 경우와 앞자리 숫자와 합쳐 두 자리 숫자로 해석할 경우. 나는 이 두 가지 경우를 따로 튜플 형태로 차례대로 구해나가는 알고리즘을 생각했다. 마지막에 이 두 가지 경우를 합해 최종 경우의 수를 구하는 것이다. for문을 돌면서 i번째 숫자를 해석하는 두 가지 경우의 수를 구한다. 이때 중간중간에 잘못된 코드를 판별하는 if문이 중요하다.

 

1. 먼저 첫 번째 숫자는 숫자가 하나밖에 없기 때문에 숫자 하나로 해석하는 1가지 경우만 있다. 따라서, (1, 0) 이 된다.

   1.1. 하지만 이때 그 숫자가 0이라면 0을 해석할 문자가 없기 때문에 이 코드는 잘못된 코드가 된다.

2. c에는 두 자리 숫자로 해석 가능한지 판단할 때 사용할 앞자리 숫자와 현재 숫자를 이은 숫자열을 담아둔다.

3. i번째 숫자가 0일 경우, i-1번째 숫자가 1 또는 2로 c가 10 또는 20이어야 한다. 왜냐하면 암호화 숫자는 1~26까지이고 이 안에 포함된 0으로 끝나는 수는 10과 20밖에 없기 때문이다.

   3.1. 10과 20이 아닐 경우, 해당 숫자는 해석할 수 있는 방법이 없기 때문에 잘못된 코드가 된다.

   3.2. 10과 20일 경우, 두 자리 숫자로 해석하는 방법만 있기 때문에 숫자 하나만 해석하는 경우는 0가지, 두 자리 숫자로 해석하는 경우는 이전에 구했던 숫자 하나로 해석하는 경우의 수가 된다. 앞에서 두 자리 숫자로 해석했던 경우는 사용할 수 없다.

ex) 220

case[0] = (1, 0)     # 2

case[1] = (1, 1)     # 2/2, 22

case[2] = (0, 1)     # 2/20

4. 마지막으로 c가 27보다 작아서 두 자리 숫자로도 해석이 가능할 경우와 27보다 커서 한 자리 숫자로만 해석 가능한 경우를 비교한다.

   4.1. 27보다 작아 두 자리 숫자로도 해석이 가능할 경우, 숫자 하나로 해석하는 경우의 수는 이전에 구한 경우의 수들의 합이 된다. 왜냐하면 숫자 하나로 해석할 경우 앞의 모든 경우에 붙어 해석 가능하기 때문이다. 두 자리로 해석할 경우는 앞에서 한 자리로 해석한 경우에만 붙어서 해석 가능하기 때문에 앞에서 한 자리로 해석한 경우의 수가 된다.

   4.2. 27보다 커 숫자 하나로만 해석 가능할 경우, 한 자리로 해석한 경우의 수는 이전에 구한 경우의 수들의 합이 되고, 두 자리로 해석하는 경우의 수는 0이 된다.

ex) 25114

case[0] = (1, 0)    # 2

case[1] = (1, 1)    # 2/5, 25

case[2] = (2, 0)    # 2/5/1, 25/1

case[3] = (2, 2)    # 2/5/1/1, 2/5/11, 25/1/1, 25/11

case[4] = (4, 2)    # 2/5/1/1/4, 2/5/1/14, 2/5/11/4, 25/1/1/4, 25/1/14, 25/11/4

5. 마지막 숫자의 경우의 수를 구해 튜플에 들어있는 두 가지 경우의 수를 합하면 최종 답이 된다.

 

 

오늘은 그래도 문제 두 개나 해결했다. 근데 알고리즘 푸는 것보다 설명하는 게 더 어려운 느낌 ㅜ 두 번째 문제 풀이 방법 쓰는데 좀 힘들었다.