아...그 뭐였더라..

99클럽 코테 스터디 4일차 TIL + DFS

https://www.acmicpc.net/problem/2468# 2468 안전영역import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**7)n = int(input())graph = []maxNum = 0 # 입력받은 높이의 최댓값 > 비for _ in range(n): graph.append(list(map(int, input().split()))) maxNum = max(maxNum, max(graph[-1])) # 각 행을 입력받으며 최댓값 구하기# 상하좌우dx = [0,0,-1,1]dy = [-1,1,0,0]def dfs(x,y,num): # num은 비가 왔을 때 잠기는 높이 visited[x][y] = True ..

https://www.acmicpc.net/problem/14495import sysinput = sys.stdin.readlinen = int(input())fibo = {}fibo[1] = 1fibo[2] = 1fibo[3] = 1for i in range(4, n+1): fibo[i] = fibo[i-1] + fibo[i-3]print(fibo[n]) n이 116 이하 자연수로 시간 초과는 나지 않았다.딕셔너리 자료구조를 이용해 풀이를 하였고 입력 받은 n까지의 수를 미리 구한 후 값을 출력했다.리스트를 사용하지 않으니 인덱스 에러가 날 확률도 적어지지 않았나.... 라는 생각이 든다....

https://www.acmicpc.net/problem/1929 import sysinput = sys.stdin.readlinem, n = map(int, input().split())for i in range(m, n+1): if i == 1: continue for j in range(2, int(i**0.5)+1): if i % j == 0 and i != j: break else: print(i) 소수는 1보다 큰 자연수 중 1과 자기자신만 약수로 가지는 수다. (자기자신만 나누어 떨어짐)입력 받은 m부터 n까지 나누어 떨어지는 수가 있는지 확인한다.제곱근까지 계산하지 않으면 시간 초과 가 발생한다.제곱근 이후로는 앞에 ..

https://www.acmicpc.net/problem/17825import sysinput = sys.stdin.readlinedice = list(map(int, input().split()))graph = [[1],[2],[3],[4],[5],[6,21],[7],[8],[9],[10],[11,25],[12],[13],[14],[15],[16,27],[17],[18],[19],[20],[32],[22], [23],[24],[30],[26],[24],[28],[29],[24],[31],[20],[32]]score = [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,13,16,19,25,22,24,28,27,26,30,35,0]an..

https://www.acmicpc.net/problem/11054import sysinput = sys.stdin.readlinen = int(input())S = list(map(int, input().split()))reversedS = list(reversed(S))incDp = [1] * ndecDp = [1] * ndp = [0] * nfor i in range(n): for j in range(i): if S[i] > S[j]: incDp[i] = max(incDp[i], incDp[j]+1) if reversedS[i] > reversedS[j]: decDp[i] = max(decDp[i], decDp[j] + 1)dec..

https://www.acmicpc.net/problem/2631import sysinput = sys.stdin.readlinen = int(input())lines = []for _ in range(n): lines.append(int(input()))dp = [1] * nfor i in range(n): for j in range(i): if lines[j] 결국 오름차순으로 정렬되기까지의 최소 이동 횟수를 정해야한다.가장 큰 증가하는 부분 수열을 구하면 그 사람은 올바르게 줄 서있는 것이기 때문에 그 나머지 값을 구하면 된다.

https://www.acmicpc.net/problem/1965import sysinput = sys.stdin.readlinen = int(input())box = list(map(int, input().split()))dp = [1] * nfor i in range(n): for j in range(i): if box[j] 가장 긴 감소하는 부분 수열, 가장 큰 증가하는 부분 수열과 비슷한 계열이다.처음 코드를 짰을 때, dp[i] = max(dp[i]+1, dp[j]) 로 적어 오답이었다.현재 자기자신과 이전 값에 자기자신이 포함되는 +1 이 되는 값 중 더 큰 값을 초기화 시키며 가장 큰 값을 구하면 된다.

https://www.acmicpc.net/problem/9461import sysinput = sys.stdin.readlinet = int(input())dp = [0] * 101dp[1] = 1dp[2] = 1dp[3] = 1for i in range(4,101): dp[i] = dp[i-2] + dp[i-3]for _ in range(t): print(dp[int(input())])n=1일 때부터 쭉 나열해 점화식을 파악할 수 있다.1 1 1 2 2 3 4 5 7 9 16 21 ..n은 100이하의 수니까 dp 리스트에 계산한 값을 초기화한다.

https://www.acmicpc.net/problem/11055import sysinput = sys.stdin.readlinen = int(input())A = list(map(int, input().split()))dp = [0] * ndp[0] = A[0]for i in range(n): for j in range(i): if A[i] > A[j]: dp[i] = max(dp[i], dp[j]+A[i]) else: dp[i] = max(dp[i], A[i])print(max(dp))dp리스트를 0으로 초기화 한 후 dp[0]값은 이전 값과 비교할 것이 없기 때문에 A[0]으로 초기화 해준다.자신 앞까지의 값을 비교하며 이전까지..

https://www.acmicpc.net/problem/11722import sysinput = sys.stdin.readlinen = int(input())A = list(map(int, input().split()))dp = [1 for _ in range(n)]for i in range(n): for j in range(i): if A[i] 자신의 앞까지 값을 비교하며 앖에서 비교했던 값중 가장 큰값 과 현재 자신의 값 + 1 중 더 큰 값을 초기화한다.이전까지 구했던 값은 다시 구하지 않고 dp 리스트를 이용해 값 비교를 해준다.