DP

[프로그래머스] 매출 하락 최소화 (DP, 트리)

https://school.programmers.co.kr/learn/courses/30/lessons/72416 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 워크숍에 참석할 직원들을 선발 모든 팀은 최소 1명 이상의 직원을 워크숍에 참석 워크숍에 참석하는 직원들의 하루평균 매출액의 합이 최소 10번 직원은 C팀과 D팀 모두에 속해 있으므로, 두 팀에서 모두 참석한 것으로 인정 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합 리턴 d[i][j] : i는 노드번호, j는 워크샵 참여/불참 하는 경우 현재 ..

[프로그래머스] 최적의 행렬 곱셈 (DP)

https://school.programmers.co.kr/learn/courses/30/lessons/12942 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 더보기 2023.04.04 - [백준/동적계획법] - [11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP) [11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP) 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 ..

[프로그래머스] 도둑질 (DP)

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 2023.07.15 - [Algorithm PS/Programmers] - 스티커모으기 (DP) 스티커모으기 (DP) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 인 karla.tistory.com 풀이 def solution(mone..

[2294] 동전 2 (동전 개수 최소값)

2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 분석 동전 교환 (DP) 분석 더보기 karla.tistory.com 풀이 """ n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 ..

동전 문제 유형 정리 (greedy, DFS, DP)

1. 여러 단위 동전, 무수히 많을 때, 교환 최소 개수 출력 2023.04.27 - [Algorithm PS/Search] - 동전 교환(DFS) 2023.05.19 - [Algorithm PS/DP] - 동전 교환 (DP) 2023.06.01 - [Algorithm PS/DP] - [2294] 동전 2 (동전 개수 최소값) 2.여러 단위 동전, 무수히 많을 때, 교환 방법 경우의 수 출력 2023.06.01 - [Algorithm PS/DP] - [2293] 동전 1 (경우의 수 구하기) 3.여러 단위 동전, 정해진 갯수, 교환 방법 경우의 수 출력 2023.05.03 - [Algorithm PS/Search] - 동전 바꿔주기 (DFS) 2023.05.03 - [Algorithm PS/DP] - [..

알리바바와 40인의 도둑 (Bottom-Up, Top-Down)

bottom up """ 알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다. N*N의 계곡의 돌다리 격자정보가 주어지면 (1,1)격자에서 (N,N)까지 가는데 드는 에너지의 최소량 만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면 3 2 5 2 3 4 6 5 2 (1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다. 5 3 7 2 1 9 5 8 3 9 2 5 3 1 2 3 5 4 3 2 1 1 7 5 ..