본문 바로가기
728x90

다이나믹프로그래밍30

[python] 백준 7579 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 해결 용량 M을 줄여야하는데 $A_{i}$ 바이트와 줄이는데 비용 $C_{i}$가 주어졌다. 이 때 최소비용을 구하는 문제 이는 배낭 문제라고 한다. https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C dp[i][j]를 i번째 물건까지 봤을 때 j요금 이하로 만들 수 있는 줄일 수 있는 메모리 합을 이야기한다. j가 i번째 메모리 사용할 때 비.. 2023. 11. 26.
[python] 백준 14267 회사 문화 1 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제 해결 노드 하나를 잡고 그것을 루트(root)로 하는 서브트리의 모든 노드에 일정한 점수를 더하는 문제 점수를 더해줄 때 DFS를 쓰면 편하다는 것은 너무 쉽게 알 수 있다. 하지만 노드 하나씩 잡고 서브트리의 모든 노드에 일정한 점수를 더하는 것은 시간복잡도면에서 비효율적이며 시간초과가 나게 되었다. 루트로 잡을 노드에 모두 점수를 주입시키고 1번이 사장이라는 것(트리의 루트)라는 것을 .. 2023. 9. 26.
[python] 백준 2159 케익 배달 https://www.acmicpc.net/problem/2159 2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 문제 해결 케익을 받는 순서는 정해져 있다. 케익을 받을 수 있는 위치는 모두 4가지이다. 그래서 출발점-도착점에 따른 최소거리를 각각 구해야한다. 받는 위치가 다르면 다음 순서에 영향을 줄 수 있기 때문 이를 구현하기 위해 가장 좋은 것은 DP이다. dist[i][j] 는 i번째 사람 케익을 받을 때 동(j=0),서(j=1),남(j=2),북(j=3),(아래 코드는 +중앙(j=4))에.. 2023. 7. 7.
[python] 백준 1398 동전 문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 동전이 1, 10, 25... 패틴을 확인 할 수 있는지 문제이다. 동전의 수열 집합을 A라 할 때 $A_{i}$ = 100$A_{i-3}$ 임을 확인 할 수 있으면 문제는 쉬워진다. 100 단위로 동전을 최대한 적은 수로 처리하는 방법을 생각하면 된다. CODE t = int(input()) coins = [1, 10, 25] # 이 형태로 계속 간다. for _ in range(t): x = int(input()) answer = .. 2023. 5. 10.
728x90