코딩 테스트48 [백준 1012번] 유기농 배추 문제 풀이 이 문제는 X, Y 가 바뀌어 있어 헷갈렸으나, DFS 문제인것을 파악하는 것은 쉬웠다. 문제를 풀때 입출력은 동일했으나, 계속 런타임 에러가 떴는데 sys.setrecursionlimit(10**6) 를 붙여 해결했다. sys.setrecursionlimit(10**6) 은 파이썬의 기본 재귀 깊이 함수가 1000으로 얕아 런타임 에러가 뜰 때, 재귀 깊이를 늘려주기 위한 방법이다. import sys sys.setrecursionlimit(10000) readline = sys.stdin.readline n = int(readline()) def dfs(x,y): if x=N or y=M: return False if arr[x][y] == 1: a.. 2023. 9. 9. [백준 1965번] 상자 넣기 문제풀이 (with Python) 이전에 풀었던 백준 11722번과 매우 유사한 문제였다. 비슷한 로직으로 뒤의 숫자가 더 크면 dp[ 뒤의 숫자 ] 와 dp[앞의 숫자] + 1 을 비교해서 더 큰 수를 저장했다. N = int(input()) arr = list(map(int, input().split())) dp = [1 for _ in range(N)] for i in range(N): for j in range(i+1, N): if arr[i] < arr[j]: dp[j] = max(dp[i] + 1, dp[j]) print(max(dp)) 2023. 8. 24. [백준 10844번] 쉬운 계단 수 문제풀이 (with Python) dp 배열을 2차원 리스트로 정의해서, 자리수에 대한 정보를 dp에 넣는 새로운 문제였다. 감이 잘 잡히지 않아 소스를 참고해서 풀었다. dp[자리수][앞 자리의 수] 값은 가능한 경우의 수이다. 1) 앞 자리가 0인 경우, dp[ i ][ j ] = dp[ i - 1 ][ 1 ] 2) 앞 자리가 1~8인 경우, dp[ i ][ j ] = dp[ i -1 ][ j -1] + dp[ i -1 ][ j +1] 3) 앞 자리가 9인 경우, dp[ i ][ j ] = dp[ i -1 ][ 8 ] N = int(input()) dp = [[0]*10 for _ in range(N+1)] for i in range(1, 10): dp[1][i] = 1 for i .. 2023. 8. 23. [백준 11722번] 가장 긴 감소하는 부분 수열 문제 풀이 with Python 각 인덱스 별로 앞의 수보다 다음 수가 작을 경우 1씩 올려준다. dp를 이용하여 dp[i]에 인덱스 i까지 가장 긴 감소하는 부분 수열의 길이를 저장한다. n = int(input()) arr = list(map(int, input().split())) dp = [1 for i in range(n)] for i in range(n): for j in range(i): if arr[j] > arr[i]: dp[i] = max(dp[i],dp[j]+1) print(max(dp)) 2023. 8. 22. 이전 1 ··· 4 5 6 7 8 9 10 ··· 12 다음
