코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 코드 def solution(board): row = len(board) col = len(board[0]) for y in range(1, row): for x in range(1, col): if board[y][x] != 0: board[y][x] += min(board[y-1][x], board[y][x-1], board[y-1][x-1]) answer = max(map(max, board)) ** 2 return answer 해설 2차원 배열을 순회하면서 '가장 큰 정사각형을 저장해야겠다' 라는 생각이 들었습니다. 처음에는 새로운 리스트를 생성..

18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 코드 import sys r = sys.stdin.readline N = int(r()) soldier = list(map(int,r().split())) dp = [] dp.append(soldier[0]) # dp = [15] for i in range(1, N): if soldier[i] = dp[j]: dp[..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 코드 import sys r = sys.stdin.readline N,*l=int(r()), for _ in range(N): l.append(list(map(int,r().split()))) max_pay = 0 dp = [0]*(N+1) for i in range(N-1,-1,-1): if i+l[i][0] > N: dp[i] = max_pay else: dp[i] = max(l[i][1] + dp[i+l[i][0]], max_pay) max_pay = dp[i] print(max_pay) 해설 처음에 dp에 어떤 값을 저장해야 할지에 대해 고민을 많이 했습니다. 처음에는 그 특정 상담 일정까지 ..

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 import sys r=sys.stdin.readline n,*l=int(r()), for _ in range(n): l.append(list(map(int,r().split()))) for i in range(1,n): for j in range(i+1): if j==0: l[i][j] += l[i-1][j] elif j==i: l[i][j] += l[i-1][j-1] else: l[i][j] += max(l[i-1][j-1], l[i-1][j]) print(max(l[-1])) 해설 인풋을 2차원 배열으로 받은 후 각 row..

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 r = sys.stdin.readline N,K = map(int,r().split()) dp = [[0 for _ in range(K+1)] for _ in range(N+1)] bag =[[0,0] for _ in range(N+1)] for i in range(1,N+1): W,V = map(int,r().split()) bag[i][0] = W bag[i][1] = ..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 코드 import sys r = sys.stdin.readline N = int(r()) num = list(map(int,r().split())) dp = [0] * N dp[0] = num[0] for i in range(1, len(num)): dp[i] = max(0, dp[i-1] + num[i]) ans = max(dp) if ans==0: print(max(num)) else: print(ans) 해설 처음에는 2차원 배열 dp를 이용해 모든 경우의 수(매 시..