본문 바로가기
  • 초부득3 - 어제보다 나은 내일을 위해
  • 꿈이 현실이 되는 날까지

sw사관학교 정글 2기/04 DP, 그리디10

[DP] 백준 연속합 1912번 with Python3 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 내 풀이 n = int(input()) arr = list(map(int, input().rstrip().split())) # print(arr) dp = [0] * n temp_stack = [] for i in range(n): temp = arr[i] if i == 0: if arr[i] >= 0: dp[i] = temp continue elif arr[i] < 0: dp[i] = temp tem.. 2021. 8. 31.
[그리디] 백준 멀티탭 1700번 with Python3 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 내 풀이 -실패- # 입력 n = 멀티탭 구멍 개수, k 전기 용품 총 사용횟수 n, k = map(int, input().rstrip().split()) # 전기 용품 사용 순서 리스트 arr = list(map(int, input().rstrip().split())) # 각 전기용품당 총 사용 횟수 use_cnt = [0] * (k+1) for i in range(k): temp = ar.. 2021. 8. 30.
[DP] 백준 RGB거리 1149번 with Python3 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 정답 풀이 n = int(input()) p = [] for i in range(n): p.append(list(map(int, input().split()))) # 0,1,2 는 각각 빨강, 초록, 파랑을 뜻함. for i in range(1, len(p)): p[i][0] = min(p[i - 1][1], p[i - 1][2]) + p[i][0] p[i][1] = m.. 2021. 8. 30.
[DP] 백준 1로 만들기 1463번 with Python3 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 내 풀이 import sys n = int(input()) a = sys.maxsize dp_table = [[a] * ((n//2)+1) for _ in range(n+1)] # dp_table[num][step] dp_table[n][0] = 1 # for i in dp_table: # print(i) for step in range(1, ((n//2)+1)): for num in range(1, n): j = n - num if j*3 2021. 8. 30.
[그리디] 백준 신입 사원 1946번 with Python3 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 정답 풀이 import sys T = int(input()) #테스트케이스 for i in range(0,T): Cnt = 1 people = [] N = int(input()) for i in range(N): Paper, Interview = map(int,sys.stdin.readline().split()) people.append([Paper, Interview].. 2021. 8. 30.
[그리디] 백준 회의실 배정 1931번 with Python3 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 내 풀이 -실패- import sys input = sys.stdin.readline n = int(input()) tmt = [list(map(int, input().rstrip().split())) for _ in range(n)] tmt.sort() ans = [] check = 0 chk2 = 0 for i in range(n): if check = end_time: cnt += 1 end_time = time[i][1] print(cnt) 출처:https://suri78.tistory.com/26 .. 2021. 8. 30.
[DP] 백준 LIS 11053번 with Python3 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 문제 내 풀이 n = int(input()) sqnc = list(map(int, input().split())) # dp = sqnc[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이 dp = [1 for _ in range(n)] for i in range(n): for j in range(i): i.. 2021. 8. 29.
[DP] 백준 점프 2253번 with Python3 ★★ https://www.acmicpc.net/problem/2253 2253번: 점프 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 www.acmicpc.net 문제 풀이 import sys input = sys.stdin.readline n, m = map(int, input().rstrip().split()) max_speed = int((2*n)**0.5) + 1 dp_table = [[float('inf')] * (max_speed+1) for i in range(n+1)] # dp_table[i][j] / [i] = 돌 번호 [.. 2021. 8. 28.
[DP] 백준 평범한 배낭 12865번 with Python3 ★ 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 N, K = map(int, input().split()) stuff = [[0,0]] for _ in range(N): stuff.append(list(map(int, input().split()))) #냅색 문제 풀이 knapsack = [[0 for _ in range(K + 1)] for .. 2021. 8. 27.

티스토리툴바