dp11 백준 4811번 : 알약 📌 알고리즘 선택 알약 n개의 경우는 알약이 n개 보다 작은 경우를 활용할 수 있므로 DP로 풀 수 있다. 📌 풀이 1️⃣ 알약이 1개인 경우 >> W H >> 1가지, dp[1] =1 2️⃣ 알약이 2개인 경우 >> W H W H >> W W H H >> 2가지, dp[2] = 2 3️⃣ 알약이 3개인 경우 큰 알약을 먹음과 동시에 3가지 케이스로 나뉘게 된다. >> 작은 알약 + 큰 알약 + 큰 알약: 남은 큰 알약 2개는 dp[2]인 경우와 같으므로 dp[0] * dp[2]로 표현할 수 있다. >> 큰 알약 + 작은 알약 + 큰 알약: 앞에 큰 알약 1개와 뒤에 큰 알약 1개는 각각 dp[1]인 경우와 같으므로 dp[1] * dp[1]로 표현할 수 있다. >> 큰 알약 + 큰 알약 + 작은 알약들:.. 2023. 6. 4. 백준 12869번 : 뮤탈리스크 | JAVA 📌 알고리즘 선택 이 문제는 빼지는 수도 3개, 빼는 숫자도 3개라 동전 문제보다 더 복잡하게 느껴졌던 문제였다. BFS를 이용하여 사용한 공격 패턴에 따라 SCV 값들을 감소시켜며 공격 최소 횟수를 구하고, DP를 이용하여 감소된 SCV 값들을 기억하여 중복 연산 횟수를 줄였다. `📌 풀이 1️⃣ scv의 수가 3개가 되도록 한다. 그래서 N이 1이나 2일 경우에는 scv의 수가 총 3개가 되도록 0을 채워준다. 2️⃣ visited[][][]의 3차원 배열을 통해 scv의 변화를 기록한다. 만약, visited[i][j][k] = 1일 경우, 0번 이상의 공격을 통해 (i, j, k)에 도달했다는 것을 의미한다. 이미 도달한 배열에 대해서는 다시 연산할 필요가 없으므로 연산을 멈춘다. 3️⃣ (i, .. 2023. 5. 31. 백준 1562번 : 계단 수 | JAVA 📌 알고리즘 선택 인접한 자리의 수를 기억하면서 풀이를 진행해야 하므로 DP를 이용해야 한다. 📌 풀이 이 문제에서 지켜야 할 규칙은 다음과 같다. 1. i번째 자리에 j라는 수가 오기 위해서는 i-1번째 자리에 j+1 혹은 j-1가 있어야 한다. 2. 0부터 9까지의 모든 수를 한 번씩 사용해야 한다. 2번 규칙을 해결하기 위해 비트마스크를 이용하여 특정 숫자를 이용했는지 아닌지를 기록하고자 한다. 비트마스크의 각 자리는 특정 숫자를 이용했는지를 나타낼 수 있고, 0부터 9까지 10개의 숫자를 확인해야 하므로 비트마스크의 자릿수는 총 10이다. 1번 규칙을 해결하기 위해 2차원 dp 배열을 이용하여 i번째 자리에 j라는 수가 있는지를 나타내고자 한다. 이를 점화식으로 나타내면 다음과 같다. dp[i][.. 2023. 5. 24. 백준 11049번 : 행렬 곱셈 순서 | JAVA 📌 알고리즘 선택 문제를 읽고 행렬의 크기를 직접 곱해보면서, 이 문제는 중복된 계산이 많고 범위를 지정해서 값을 기억해야 하기에 무조건 2차원 dp로 풀어야겠다는 생각이 들었다. 그런데 구현 하기가 너무 어려웠다.. 이런저런 생각을 하다보니 트리까지도 그리게 되었는데 행렬의 크기를 담은 배열을 마음대로 수정하다보니 마음처럼 결과가 안나오더라.. 아직 좀더 연습이 필요한 것 같다! 📌 풀이 아쉬운 마음에 올려보는 ,, 나의 트리 ,, 재귀로 풀어보고 싶은데 재도전 해봐야겠다. 아무튼 결국은 2차원 배열을 사용한 dp로 풀었으니,, 해당 풀이를 설명해보자. 이 문제에서 중요한 것은 dp[i][j]에 값을 채워나가는 것인데, dp[i][j]는 i번째 행렬에서 j번째 행렬까지의 크기의 곱 중 최솟값을 담는다... 2023. 4. 8. 백준 10942번 : 팰린드롬? | JAVA 📌 알고리즘 분류 본 문제는 언뜻 보면 구현 문제처럼 보이지만,, 질문 개수의 범위가 크기 때문에 중복 계산을 줄이는 과정이 절대적으로 필요하다. 그에 따라 dp로 풀어야 한다. 하지만 1차원 배열의 dp가 아닌, 2차원 배열의 dp를 떠올릴 수 있어야 한다. 아래의 풀이에서 자세히 살펴보자. 📌 풀이 우선, 팰린드롬이란 우리말로 회문이며, 거꾸로 읽은 것과 제대로 읽은 것이 같은 것을 말한다. 각 문제에서 주어진 범위의 수열에 대해 하나씩 비교를 하면 시간초과가 난다. (직접 확인했다 ..ㅜㅜ) 그래서 중복 계산을 줄여주어야 하는데, 이 문제에서 중복 계산을 줄이려면 각 문제마다 해당 범위의 수들에 대해 비교를 해주기 보단, 한 번에 모든 범위의 수에 대한 비교를 마친 후 각 문제의 범위에 대해서는 팰.. 2023. 4. 4. 백준 7579번 : 앱 | JAVA 📌 알고리즘 선택 '평범한 가방' 문제와 유사한 문제로 친구에게 추천 받은 문제이다. 그래서 dp를 사용한다는 것을 알고 접근했다. 분명히 비용과 앱의 개수? 등이 기준이 될텐데, 어떻게 dp 배열을 만들고 채워할지에 대해 많이 고민했다. 📌 풀이 처음에는 '평범한 가방' 문제의 풀이를 떠올리며 2차원 배열로 문제를 해결해야겠다고 생각했다. 문제의 조건을 자세히 보면, 앱 메모리의 크기를 기준으로 두기에는 범위가 너무 넓어서 적절하지 않다. 그래서 비용과 앱을 어디까지 사용했는지를 기준으로 두고, 배열의 값을 앱 메모리의 크기로 채우고자 했다. 그런데 ,,, 아무리 생각해도 2차원 배열의 필요성을 모르겠어서 1차원 배열로 다시 시도해봤다. 1차원 dp 배열의 인덱스는 비용, 값은 해당 비용을 사용해서 확.. 2023. 3. 29. 이전 1 2 다음
