dp

[프로그래머스] 숫자 변환하기 [python]

문제 문제는 간단했다. x를 더 큰 수로 만들 수 있는 방법은 3가지 있고, y라는 target 수에 도달하는 방법 중 최소 연산을 한 값을 구하는 거 였다. DP로 풀었다. memorize로 값들을 1억으로 초기화를 했고, 시작하는 수인 x를 0으로 설정하고, 세가지 연산을 진행하였다. 현재 계산하는 값이 1억이면 도달할 수 없는 수 이기 때문에 넘어가고, 현재까지 도달하는 데 연산 수 + 1 과 도달할 수에 저장된 값을 비교하여, 작은 값을 현재 연산 수로 저장하였다. 코드 def solution(x, y, n): answer = 0 memorize = [1e9] * (y+1) memorize[x] = 0 for i in range (x, y+1): if memorize[i] == 1e9: conti..

[백준] 2629번 양팔저울 풀어보기 [Java]

관계식이 있는 dp문제였다. 관계식만 잘 구하면 잘풀수 있어 골드3까지는 아닌거 같다!!(내가 뭐라고 평가하나,,,,ㅋㅋㅋ) 👨‍🏫 풀이 나는 세가지 경우를 나눠서 풀었다. 1. 지금 추를 더하는 경우 2. 지금 추를 더하지 않고 넘어가는 경우 3. 지금의 무게가 추보다 작다면, 추에서 현재 무게를 빼고, 크다면, 현재 무게에서 추를 뺀다. Base case 1. weight 음수가 되면 안되고(원래 0이 될일도 없기 때문에 0을 포함해줘야 됐지만, 나는 첫 시작 무게를 0으로 설정을 해줘서 0을 포함해주지 않았다.) 40000보다 크면 안된다. 2. 주어진 추는 한번만 사용가능하기 때문에 주어진 추를 다 방문했는지 체크 👨🏻‍💻 코드 package 번2629; import java.io.Buffered..