#2688

처음 접근 방식 : n의 입력값에 따라 숫자를 순회한다
=> 브루트포스

풀이 1 코드

N = int(input())
answerList = []

for i in range(0, N):
    cnt = 0
    X = int(input())
    maxNum = ""
    for i in range(0, X):
        maxNum += "9"
    maxNum = int(maxNum)
    
    for i in range(0, maxNum + 1):
        # 000부터 999까지 하나씩 돌아 => 큰 루프
        
        i = str(i)
        num = i.zfill(X)
        # print("<start> inputnum = ", num)
    
        # 체크하는 알고리즘
        for j in range(0, X-1):
            # print("j = ", j)
            # num 하나에 대해서 for 문 돌면서 체크

            if num[j] <= num[j+1]:
                # 조건 맞아? 
                # print("num[", j, "] > num[", j+1, "] , => ",num[j], " ", num[j+1] ," 조건 맞아")

                if j == X-2:
                    # print("num[", j, "] > num[", j+1, "] , => ",num[j], " ", num[j+1] ," 끝까지 돌았고 마지막까지 조건 맞아")
                    cnt += 1
                else: 
                    continue
            
            else:
                # print("num[", j, "] > num[", j+1, "] , => ",num[j], " ", num[j+1] ," 조건 안맞아")
                break

    answerList.append(cnt)

        # 조건 맞으면 cnt += 1

for a in answerList:
    print(a)

당연히 시간초과.. 문제 풀기 전에 조금만 더 깊게 생각해보자 제발 ..

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다.
각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

첫 번째 풀이 => 시간 초과

64자리 숫자를 다 돈다고 쳤을 때 그 숫자 하나당 안에 문자열을 도니까 그런가?

예를 들어 최악의 경우에

1000
64
64
64
~~
64

이렇게 입력이 주어지면?

일단 대충이라도 짱구를 굴려보면 당연히.. 말이 안된다.
진짜 간단하게는 T = 1000 이고? n = 64 일 때,
< for i (0, 대략 100억?) > 을 1000번 한다는 소린데 당연히 안된다..

왜 이렇게 당연한걸 생각을 못했을까? 이전에 풀었던 문제와 매우 유사하다고 생각한다.

핵심은 바로

n으로 얼마가 주어지던 간에 이미 정답은 정해져 있다.
그럼 나는 잘 보고 특별한 규칙이 있는지? 있다면 그 규칙을 찾으면 된다.

생각의 흐름

0 일 때 -> 10개
1 일 때 -> 9개
2 일 때 -> 8개
...

이미 했던 연산을 그대로 가져와서 사용한다.
=> DP

DP (동적 계획법, Dynamic programming)
이미 했던 연산을 계속 반복, 저장해두고 또 써먹는다.
"기억하며 풀기"라고도 한다.

DP 에 대해서는 다음에 따로 공부를 해보자.
< 재귀, 그리디와 함께 비교,대조하여>

풀이 2

answerList = []

for i in range(int(input())): 
    n = int(input())
    # n = 4

    dp = [[0 for i in range(0, 11)] for i in range(0, n+1)]

    if n == 1: 
        answerList.append(10)
        break

    dp[1] = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    dp[1].append(sum(dp[1]))
    dp[2] = [ 10, 9, 8, 7, 6 ,5, 4, 3, 2, 1]
    dp[2].append(sum(dp[2]))

    for i in range(3, n+1):
        for j in range(0, 10):
            if j == 0:
                dp[i][j] = dp[i-1][10]
            else:
                dp[i][j] = dp[i][j-1] - dp[i-1][j-1]
        dp[i][10] = sum(dp[i])
        # print( "dp[", i, "][10] = ", dp[i][10])
    
    # for i in range(0, n+1):   
        # print(dp[i])
    answerList.append(dp[n][10])

for i in answerList:
    print(i)

코드를 줄이고, 예쁘게 하기 위한 한 가지 팁을 적어둔다.
다음에 써먹자!!!

• 입력값 주어졌을 때 그만큼 for 문 돌기
  => for i in range(int(input())):
  변수 따로 하나 안만들고 그냥 바로 넣어버리자, 어차피 한번 쓰고 안쓰지 않나?

• 코드 길이 줄이기
  dp = []
  for i in range(0, 10):
  dp.append(1)
  이걸 조금이나마 간단하고 짧게 줄여서?
  dp = [1 for i in range(10)]

• n 입력 받아서 n개 열(row)의 정해진 개수(col)만큼의 배열 생성하기
  n = int(input())
  dp = [[0 for i in range(0, 11)] for i in range(0, n+1)]