728x90

백준 243

백준 14501 <퇴사> Python

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 일이 끝나는 날부터 마지막 날 까지 모든 날을 채워가며 업데이트 해야하는 점이 냅색 알고리즘(배낭문제) 와 비슷했습니다. 이 점만 생각하면 쉽게 풀 수 있습니다. def solution(N, data_list): # DP memo = [0 for _ in range(N+1)] # 일의 번호, data_list 인덱스 for work in range(N): # n 번째 시작한 일이 끝나는 날 end_day = work + data_list[work][0] # 퇴사하기 전에 끝날 경우에만 if end_day

백준 11053 <가장 긴 증가하는 부분 수열> Python

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 https://dev-diary-0717.tistory.com/34 백준 11055 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, ..

백준 9461 <파도반 수열> Python

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 그림을 보며 규칙을 알아내기만 하면 쉽게 풀 수 있습니다. def solution(T, data_list): # 데이터 리스트 중 최댓값 max_list = max(data_list) # DP memo = [0 for _ in range(101)] # 앞부분 채우기 memo[0:6] = [1, 1, 1, 1, 2, 2] i = 6 while True: # 중단조건 if i == max_list + 1:..

백준 2193 <이친수> Python

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 경우의 수를 나누는 기준만 잘 세우면 쉽게 풀 수 있는 문제입니다. def solution(n): # DP memo = [0 for _ in range(91)] # 앞 부분 미리 작성 memo[1] = 1 memo[2] = 1 i = 3 while True: # 중단 조건 if i >= n+1: return memo[n] # 맨 앞은 10 으로 고정되어 있음 # 그 뒤를 생각해야 하는데..

백준 11727 <2Xn 타일링 2> Python

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net https://dev-diary-0717.tistory.com/26 BaekJoon 11726 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방 dev-diary-0717.tistory.com 2xn 타일링 문제의 연장선상에 있는..

백준 1932 <정수 삼각형> Python

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 전형적인 DB 문제입니다. 위에서부터 아래로 점점 더해가며 비교하면 쉽게 풀 수 있습니다. def solution(n, data_list): # DP memo = [[0]*(i+1) for i in range(len(data_list))] # 최상단 채워주기 memo[0][0] = data_list[0][0] # 아래로 내려가면서 더함 # n 층에서 n+1 층으로 더함 for i in range(n-1): for j in range(len(data_list[i])): ..

백준 12852 <1로 만들기 2> Python

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net '1로 만들기' 와 같은 풀이지만 역산하며 경로를 출력하는 과정이 추가되었습니다. https://dev-diary-0717.tistory.com/20 BaekJoon 1463 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP 알고리즘의 전형적인 문제입니다. 어떤 조건에서 이전 단계와 dev-diary-0717.tistory.com def solution..

백준 11726 <2Xn 타일링> Python

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 어떤 경우의 수로 나눠서 풀어야할지만 생각하면 간단하지만 이를 생각하기가 어려운 문제였습니다. 마지막에 오는 타일의 모양을 생각하면 쉽게 풀 수 있습니다. def solution(n): # DP memo = [0 for _ in range(n+1)] # 2까지만 채우기 memo[1] = 1 if n == 1: return memo[1] memo[2] = 2 # i 번째 맨 뒤가 = 모양이면 # (i-2) 가지 이고 #..

백준 11659 <구간 합 구하기 4> Python

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 누적합 알고리즘을 알고있다면 간단한 문제였습니다. def solution(N, M, num_list, data_list): # 누적합 리스트 만들기 sum_list = make_sum_list(N, num_list) # i ~ j 구간의 합은 (j 까지의 누적합) - (i-1 까지의 누적합) for i, j in data_list: print(sum_list[j] - sum..

백준 2579 <계단 오르기> Python

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net def solution(N, data_list): # memo 와 자릿수 맞추기 data_list = [0] + data_list # DP # 2 까지는 미리 채우기 memo = [0 for _ in range(N+1)] memo[1] = data_list[1] # N 이 1이면 if N == 1: return memo[1] memo[2] = memo[1] + data_list[2] # N 이 2면 if N ..

728x90