![]()
푼 날짜 : 2024.10.25푼 문제 : [1890] / 점프사용한 언어 : python알고리즘 : DP 점화식 :dp[i+num][j] += dp[i][j] (if i + num dp[i][j+num] += dp[i][j] (if j + num 현재 위치에서 이동 가능 숫자(num)만큼 뛰었을 때 범위를 벗어나지 않는 경우 현재 값을 더해준다. 코드 :N = int(input())graph_ = []for _ in range(N): row = list(map(int, input().split())) graph_.append(row)dp = [[0 for _ in range(N)] for _ in range(N)]dp[0][0]=1 # 가장 왼쪽 위 칸에서 출발하므로 시작 1로 초기화..
![]()
푼 날짜 : 2024.10.12푼 문제 : [2096] / 내려가기사용한 언어 : python알고리즘 : DP 접근 방식 :처음에 일반적인 DP로 풀다가 메모리 초과가 났다.생각해보면 DP는 현재값 계산을 위해 이전 값을 활용하기 때문에 다음 계산 전 현재 값을 이전 값으로 덮어씌웠다.# 덮어쓰기dp[0][0] = dp[1][0]dp[0][1] = dp[1][1]dp[0][2] = dp[1][2]dp2[0][0] = dp2[1][0]dp2[0][1] = dp2[1][1]dp2[0][2] = dp2[1][2] 이렇게 하면 모든 DP 배열을 채우지 않고 단순하게 계산할 수 있다. 코드 :import sysN = int(sys.stdin.readline())dp = [[0, 0, 0], [0, 0, 0]]..
![]()
푼 날짜 : 2024.07.25푼 문제 : [14940] / 쉬운 최단거리사용한 언어 : python 푼 방법 :너비 우선 탐색으로 접근하였다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력 처음에는 리스트 형식( [1, 2, 3, ~] )으로 출력을 잘못해서 틀렸고, 두 번째에는 위의 예외처리를 안해줘서 틀렸다. 항상 문제를 꼼꼼하게 읽자! 코드 :import sysfrom collections import dequeN, M = map(int, sys.stdin.readline().split())graph_ = []visited = [[0 for _ in range(M)] for _ in range(N)]dx = [1, -..
![]()
푼 날짜 : 2024.07.22푼 문제 : [11726] / 2×n 타일링 1사용한 언어 : python 점화식:dp[i] = dp[i−1]+dp[i−2] (i≥2) 어떻게 구했냐면... 코드 :import sysN = int(sys.stdin.readline())dp = [0 for _ in range(1000+1)]dp[1] = 1dp[2] = 2dp[3] = 3dp[4] = 5for i in range(5, N+1): dp[i] = dp[i-1] + dp[i-2]print(dp[N]%10007) DP는 마냥 어렵다고 생각했는데 하다보니 너무 재밌다...(?) [ DP 풀 때 중요한 것 ]1. 점화식을 잘 세우자! 2. 초기값을 잘 설정해주자!
