1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 코드 import heapq import sys r = sys.stdin.readline N,*_heap = int(r()), heapq.heapify(_heap) for _ in range(N): x = int(r()) if x == 0: if len(_heap) == 0: print(0) else: print(heapq.heappop(_heap)) else: heapq.heappush(_heap, x) 해설 처음으로 Heap 구조 문제를 ..

코딩테스트 연습 - 가장 큰 정사각형 찾기 [[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..

2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 코드 import sys r=sys.stdin.readline N=int(r()) l=list(map(int,r().split())) l.sort() money=1 for i in l: if money < i: break money += i print(money) 해설 입력받은 리스트 l 을 오름차순으로 정렬한 후에 weight 의 초기값을 1로 두고 포문을 이용해 리스트 안 요소와 weight 를 비교하였다. 만약 리스트의 요소가 weight 보다 크다면 측정할 수 없는..