매일 성장하자!!

문제 풀이 이 문제는 dp문제로, 바텀업(반복문)을 통한 메모이제이션으로 풀수 있습니다. 큰 문제를 작은문제로 나누는데 항상 결과가 같기 때문입니다.(반대로 큰문제를 풀기위해 작은문제를 사용하는 것이 문제가 없다라고 생각해도 좋습니다.) 무슨말이냐면, 미지의 번호인 i번째에 포도주를 먹는데 i - 1, i - 2 ...이전의 포도주를 먹는 최대값이 사용될수 있다는 의미입니다. 저는 항상 dp문제를 보면 미지의 번호인 i번째의 최대값을 구하는데 어떤 이전의 값들이 사용될까를 생각합니다. 이 문제는 '연속된 세개의 포도주를 먹을수 없다'라는 제한조건만 잘생각해보면 됩니다. i - 3i - 2i - 1i 안먹음먹음먹음 안먹음먹음 안먹음 그렇다면 이런식으로 세가지 경우로 나눌수 있습니다. 표에 입..

문제 풀이 맨 위에서부터 한 레벨씩 내려가면서, 왼쪽 아래, 왼쪽 오른쪽의 합을 더하며 dp 테이블에 값을 저장하면 된다. 높이는 최대 500이고, 내려가면서 현재 높이의 개수 * 2만큼 탐색하므로(2 + 4 + 6 + 8 + ... + 1000) 시간초과 날 걱정은 안해도된다. 물론 문제에서 풀라는 것과같이 이미 값이 있으면 최대값으로 dp 테이블을 갱신해 나가며 풀면된다. 반복문을 이용한 bottom up으로 dp테이블에 값을 적어가며 메모이제이션을 구현했고 해당 메모된 값을 계속 업데이트하며 문제를 풀었다. 나는 ArrayList를 이용했다. 코드 package baekjoon.DP; import java.io.BufferedReader; import java.io.IOException; impor..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 dp로 풀면 시간초과가 나지않을수 있다. 일단 현재 어떠한 수를 i(1 과 입력되는 N사이의 임의의 수) 라 하면 i의 연산의 최소횟수는 i - 1 수의 연산의 최소횟수, i / 3(나머지가 0이라면) 수의 연산의 최소횟수, i / 2(나머지가 0이라면) 수의 연산의 최소횟수의 의 가장 작은 값에 + 1을 한것이다. 그리고 연산되는 방법의 수는 List list = new ArrayList();로 Li..

문제 문제에 주어진 꿍 피보나치를 통해서 주어진 입력에대한 답을 구하면된다. 꿍 피보나치는 d[n] = d[n - 1] + d[n - 2] + d[n - 3] + d[n - 4]이다. 풀이 귀여운 꿍문제를 어떻게풀까? 피보나치 문제기 때문에 dp테이블에 메모이제이션해나가며 풀면 시간초과가 나지않겠다. 바텀업으로 반복문으로 풀었당! (재귀함수로 풀어도됩니당!) 타입에 주의해야한다. 코드 package baekjoon.DP; import java.io.*; public class Main9507 { static int T; static long[] d = new long[70]; public static void main(String[] args) throws IOException { BufferedRead..