No Limitation

https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr Example 6명의 사람이 있고 7, 10의 경우를 생각해보면 시간을 1≤ t ≤ 60(6명*10분) 범위 내에서 선택해서 적용한다 가정하면 예를 들어 중간 값인 30분을 할당할 수 있다고 하면 7의 경우 4명을 담당할 수 있고 10의 경우 3명을 감당할 수 있다. 따라서 각자 담당할 수 있는 사람의 합은 7명이고 이는 6명보다 더..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 본 문제를 푼 관점은 다음과 같이 풀어보았습니다. 처음에는 단순 완전 탐색 문제라고 생각을 했습니다. 예를 들어보면 다음과 같은 예제가 있다고 하면 현재는 2, 1, 3 제품에 대한 멀티탭을 꽂은 상황입니다. 여기서 예를 들어 다음으로 4를 꽂아야 할 차례인데 4는 현재 멀티탭을 꽂을 곳이 없습니다. 따라서 코드를 빼야하는 상황이 생기는데 이 코드를 빼는 횟수를 최소화를 해야합니다. 그래서, 처음..

https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 참고 포스팅 https://hjp845.tistory.com/167 https://ngwoon.github.io/boj/2021/04/07/BOJ-%EA%B1%B0%EB%A6%AC/ B O J 순으로 가 최종 목적지에 도달할 때 드는 가장 최소의 비용을 계산하는 문제이다. B - O - J 로 가는 경우의 수를 Greedy하게 푸는 것이 가장 최적이라고 생각했지만 다음 반례를 생각해보면 Greedy가 최적의 solution을 보장해주지 못한다. 다음 반례를..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 동전 1과 유사한 유형으로 생각하면 된다 https://yscho.tistory.com/37 [DP] 동전 1 - 백준 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 참고 포스팅 https://j2wooooo.tistory.com/42 결국 이 문제 역시 점화식으로 푸는 문제였다. 각 일별 최적의 수익을 정리하기 위해서는 다음 논리로 갈 수 있다. 예를 들어 x일 날의 최적의 수익은 다음 중 하나이다. x일 상담 끝나는 날짜가 퇴사 일을 넘기는 경우 → x일의 최적의 수익은 x+1일의 최적의 수익과 동일하다 ( dp[x] = dp..

https://programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 전에 월간 코드 챌린지를 참여했을 땐 시간 부족으로 풀지 못했던 문제인데 기회가 생겨 다시 풀게 되었다. 당시는 규칙을 찾으려고 발버둥을 쳤던 문제였는데 단순 구현 문제였다. 논리는 단순하다. 우선 다음과 같이 0을 담고 있는 빈 삼각형을 만들어준다. 다음으로 [1] 첫 번째 요소를 채워주는 반복문을 구축한다. [2] 다음으로 마지막 element요소를 채워주는 반복문..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 반례와 많이 씨름을 했던 문제이다. 다음 문제는 동전을 이용하여 주어진 수를 구축할 때 가장 최소가 되게 하는 문제로 굉장히 단순한 유형에 속했지만 반례를 대응하지 못해 한동안 고생했던 문제였다. 논리는 다음과 같다. 4200원을 만들기 위해 1000원, 300원 1원이 주어졌다고 하면 Greedy의 논리를 빌려 가장 큰 1000원이..

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 Knapsack 문제의 전형적인 예시다. 메모이제이션을 이용하여 recursion을 통해 구현하였다. 본 문제는 정석적인 문제라 형태를 외워놔도 좋을 것 같다. n, k = [int(x) for x in input().split()] weight = []; value = []; dic = {}; for _ in range(n) : ..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 다음 문제는 Dynamic Programming으로 푸는 문제인지는 잘 모르겠지만 여기서는 단위 3, 5를 기반으로 푸는 것이라는 아이디어는 DP에 기초함 예를 들면 다음을 생각해보자 18을 만들어야 하는데 3, 5단위로 만들려면 3을 6번 쓸 때 5번 쓸 때,... 이럴 때 5로는 어떻게 만들고 이런 경우의 수를 계산해주면 문제는 간단히 구현된다 N = int(input()) i = 1 while 3*i ..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 이러한 DP 문제에서 경우의 수를 다루는 문제를 익혀야 한다...! 여기서도 5를 1번만 쓴 경우 만드는 경우의 수 [5] 5를 2번 쓴 경우 만드는 경우의 수 [55, (5+5), (5-5), (5/5), (5*5)] 이렇게 경우의 수를 생각해볼때 5를 3번 쓴 경우를 만드는 경우의 수는 다음과 같다 555를 먼저 추가해주고 [5] 와 [55, (5+5), (5-5), (5/5), (5*5)] 사이의 사칙연산 (+, -, /, *) [55, (5+5), (5-5), (5/5), (5*5)] 와 [5] 사이의 사칙연산 (+, -, /, *)..