728x90
반응형
※ 문제링크
※ 관련개념
※ 참고 사이트
해당문제는 메모이제이션과 배열을 활용하여 푸는 문제였다. 문제이름은 쉬운 계단수인데 풀어보니 해결방법이 너무 어려웠다. 처음 생각했던 방법은 리스트로 숫자를 받아서 계속해서 갱신하여 푸는 방법이었는데, 답은 잘 나왔으나 시간초과로 실패했다. 해결방법을 고민해도 도저히 답이 나오지 않아 구글링을 통해 문제를 해결했는데, 내가 발견하지 못한 규칙이 존재했고, 해당 규칙을 파악하면 생각보다는 쉽게(?) 풀 수 있는 문제였다. 이번 문제를 풀면서 단순히 메모이제이션만 쓴다고 해서 효율적으로 코드를 작성할 수 없다는 것을 다시 알 수 있었으며, 부족한 부분을 확인할 수 있는 기회였던거 같다. 내가 실패했던 코드와 참고한 사이트의 코드는 아래와 같다.
# 단순 메모이제이션을 통해 푸는 방법 # 시간초과
N = int(input())
dp = [str(i) for i in range(1, 10)]
cnt = 1
while N > cnt:
dp_next = []
for i in range(len(dp)):
if dp[i][-1] == '9':
dp_next.append(dp[i][-1] + str(int(dp[i][-1]) - 1))
elif dp[i][-1] == '0':
dp_next.append(dp[i][-1] + str(int(dp[i][-1]) + 1))
else:
dp_next.append(dp[i][-1] + str(int(dp[i][-1]) + 1))
dp_next.append(dp[i][-1] + str(int(dp[i][-1]) - 1))
dp = dp_next[:]
cnt += 1
print(len(dp) % 1000000000)
# 1~9까지의 숫자가 각각의 자릿수마다 얼마나 올수 있는지를 확인하여 푸는 방법 # 통과가능
N = int(input())
dp = [[0 for i in range(10)] for k in range(101)]
for i in range(1, 10):
dp[1][i] = 1
for i in range(2, N + 1):
for j in range(10):
if j == 0:
dp[i][j] = dp[i - 1][1]
elif j == 9:
dp[i][j] = dp[i - 1][8]
else:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
print(sum(dp[N]) % 1000000000)
P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 2579번 계단 오르기 / 사용언어 : 파이썬(python) (0) | 2021.12.23 |
---|---|
[BOJ] 11053번 가장 긴 증가하는 부분 수열 / 사용언어 : 파이썬 (0) | 2021.12.23 |
[BOJ] 1463번 1로 만들기 / 사용언어 : 파이썬(python) (0) | 2021.12.23 |
[BOJ] 1149번 RGB거리 / 사용언어 : 파이썬(python) (0) | 2021.12.23 |
[BOJ] 1932번 정수 삼각형 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
댓글