1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1로 된 가장 큰 정사각형의 크기 출력 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 import sys input=sys.stdin.readline n,m=list(map(int, input().split())) d=[[0 for j in range(1001)] for i in range(1001)] max=0 # 변의 길이 for i in range(0,n): # 세로 arr=list(input()) for j in range(0,m): # 가로 d[i][j]=int(arr[j]) if d[i][j]==1 and j>..

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 분석 L[N] : 왼쪽에서부터 N을 포함한 최대 연속 합 L[i]= max(A[i], L[i-1]+A[i]) R[N] : 오른쪽에서부터 N을 포함한 최대 연속 합 R[i]= max(A[i], R[i+1]+A[i]) L[N-1] + R[N+1] : N을 1개 제거한 최댓값 (1개의 수를 삭제할 수 있기 때문) [1912번] 연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 ..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n = int(input()) list = list(map(int, input().split())) dp = [0] * n # 최대 연속합 dp[0] = list[0] for i in range(1, n): dp[i] = max(list[i], dp[i-1]+list[i]) # list[i] / 이전최대연속합 + list[i] # print(dp) print(max(dp))

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 분석 D[N][H] : 길이가 N인 계단에서 H높이로 종료되는 계단 수를 만들 수 있는 경우의 수 D[i][0] : 0인 경우, 뒤에 1만 올 수 있음 ➔ D[i][1] D[i][j] : 1~8인 경우, -1, +1 높이 올 수 있음 ➔ dp[i][j]= dp[i-1][j-1] + dp[i-1][j+1] D[i][9] : 9인 경우, 뒤에 8만 올 수 있음 ➔ D[i][8] 풀이 import sys input=sys.stdin.readline # 길이 n=int(input()) # dp[계단길이][계단높이] dp=[[0 for j in range(11)] for i in ran..

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 분석 D[N] : 길이 N으로 만들 수 있는 타일의 경우의 수 D[N-1] : n-1까지 타일이 채워져있는 경우 ➔ 새로운 타일 1개를 채워 N길이를 만듦 D[N-2] : n-2까지 타일이 채워져있는 경우 ➔가로로 타일 2개를 래워 N길이를 만듦 D[N] = D[N-1]+D[N-2] 풀이 # 2*n크기 직사각형을 2*1/1*n으로 채우는 방법의 수 n = int(input()) d=[0]*1001 # n의 최댓값 1000 d[1]=1 d[2]=2 for i in range(3, n+1..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net bottom up n = int(input()) s = [list(map(int, input().split())) for i in range(n)] dp = [0 for _ in range(n+1)] for i in range(n): for j in range(i+s[i][0], n+1): if dp[j] < dp[i] + s[i][1]: dp[j] = dp[i] + s[i][1] print(dp[-1]) top down n = int(input()) dp = [0]*(n+2) # 오늘부터 퇴사일까지 벌수있는 최대수입 (점화식 테이블) t=[0]*(n+1) # 상담에 필요한 일수 p=[0]*(n+1)..