공대생

https://www.acmicpc.net/problem/2579내 코드let N = Int(readLine()!)!var S: [Int] = []var dp: [Int] = Array(repeating: 0, count: N)for _ in 0..Review처음에는 아래 사진 처럼, 가지치기 형식으로 풀었습니다.하지만 가지치기 단계에서 같은 연산이 반복되는 중복되는 과정도 있었기 때문에다이나믹 프로그래밍(DP) 방식으로 생각을 돌렸습니다.문제의 조건은 아래와 같습니다.1. 계단을 오를 때, 한 번에 1 계단, 2 계단 씩 오를 수 있습니다.2. 한계단씩 3번 연속으로 오를 수 없습니다.예를 들어, 한 번에 계단 1, 2, 3을 모두 밟으면 안 됩니다.점화식 마지막 계단을 밟기 전의 상황을 생각해 본다면..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 내 답안 import sys input = sys.stdin.readline dp = [0] * 91 dp[0] = dp[1] = 1 N = int(input()) if N < 3: print(dp[N-1]) else: for i in range(N-2): dp[i+2] = dp[i+1] + dp[i] print(dp[N-1]) REVIEW 6자릿수까지 노가다 했는데, 결론은 규칙이 있..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 내 답안 import sys input = sys.stdin.readline dp = [0] * 101 dp[0] = dp[1] = dp[2] = 1 for i in range(int(input())): n = int(input()) if n < 3: print(dp[n]) else: for i in range(n-2): dp[i+3] = dp[i] + dp[i+1] print(dp[n-1]) REVI..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 내 답안 import sys input = sys.stdin.readline n = int(input()) dp = [list(map(int,input().split())) for i in range(n)] for i in range(n-1, 0, -1): for j in range(i): dp[i-1][j] += max(dp[i][j], dp[i][j+1]) print(dp[0][0]) Review 맨 아래서부터 둘 중의 한값중 큰 값을 그 윗 값에 더하는 것을 반복..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 내 답안 dp = [0, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0] for i in range(int(input())): n = int(input()) if n == 1 or n == 2 or n == 3: print(dp[n]) else: for i in range(4, n + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] print(dp[n]) 처음 접근할 때는 DFS로 돌려서 풀었다. DFS를 돌려보니 규칙이 보였고, 직접 n == 5 인 경우..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 내 답안 N = int(input()) x = list(map(int, input().split())) for i in range(1, N): x[i] = max(x[i], x[i] + x[i - 1]) print(max(x)) 사실 처음에 코드 짤 때는 N = int(input()) x = list(map(int, input().split())) dp = [0] * N for i in range(1): f..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 내 답안 import sys input = sys.stdin.readline N, K = map(int, input().rstrip().split()) dp = [0] * (K + 1) for _ in range(N): W, V = map(int, input().rstrip().split()) for i in range(K, W -..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 내 답안 import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) dp = [0] * N dp[0] = A[0] for i in range(1, N): for j in range(i): if A[i] > A[j]: dp[i] = max..

https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 내 답안 import sys input = sys.stdin.readline N = int(input()) A = [int(input()) for i in [0]*N] dp = [1] * N for i in range(1, N): for j in range(i): if A[i] > A[j]: dp[i] = max(dp[i], dp[j]+1) print(N-max(dp)) 가장 긴 증가하는 부분 수열의 원..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 내 답안 import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) dp = [1] * N for i in range(1, N): for j in range(i): if A[i] > A[j]: dp[i] = max(d..