dp60 [자바] 백준 27501 - RGB트리 (java) 목차문제 : boj27501 필요 알고리즘트리 DP (트리 + 동적계획법)트리에서 DP를 사용해 푸는 문제이다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 '백준 1149 RGB거리' 문제의 트리버전이라고 보면 된다. 그러니 저걸 안풀었다면 저것부터 풀어보자. 1149를 못푸는데 이 문제를 풀 수 있을 가능성은 없다. 우선 간소화해서 생각해보기 위해, 이 문제를 1149번 문제처럼 트리긴한데 그냥 1차원이었다고 생.. 2024. 5. 23. [자바] 백준 11909 - 배열 탈출 (java) 목차문제 : boj11909 필요 알고리즘DP (동적 계획법)DP를 알고 있다면 쉽게 해결 가능한 문제이다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 need(X, Y)를 X 좌표에서 Y 좌표로 갈 때 필요한 비용이라고 하자. 예를들어 X가 (1,1), Y가 (1,2) 이고, 배열의 값이 각각 3과 5였다면 need(X, Y)는 3이다. 이 때 dp[a][b]는 (a, b) 좌표로 가는데 필요한 최소 비용이라고 .. 2024. 5. 14. [자바] 백준 14728 - 벼락치기 (java) 목차 문제 : boj14728 필요 알고리즘 DP, 냅색 (배낭 문제) DP로 해결 가능한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 dp[x]를 x시간을 사용해 얻을 수 있는 최대 점수라고 해보자. 그렇다면 현재 단원에 대한 K와 S가 주어졌을 때, x시간을 사용해 얻을 수 있는 최대 점수는, '현재까지 파악한 x시간을 사용해 얻을 수 있는 최대 점수', 'x-K 시간까지 얻을 수 있는 최대 점수에 이번 단원.. 2024. 4. 8. [자바] 백준 24956 - 나는 정말 휘파람을 못 불어 (java) 목차 문제 : boj24956 필요 알고리즘 DP (동적 계획법) DP로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 'WHE'가 가능한 경우의 수를 찾는다고 생각해보자. 이 경우 매우 직관적으로 가능한데, 하나씩 문자를 살펴보면서 'W'라면 이전까지 나온 W의 수+1, 'H'라면 현재까지 'WH'가 가능했던 경우의 수 + 이전까지 나온 'W'의 수, 'E'라면 현재까지 'WHE'가 가능했던 경.. 2024. 2. 24. [자바] 백준 1309 - 동물원 (java) 목차 문제 : boj1309 필요 알고리즘 DP (동적계획법, 다이나믹 프로그래밍) 기본적인 형태의 DP 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 Nx2 칸으로 동물원이 구성된다. N칸의 세로는 우선 생각하지 말고, 2칸인 가로칸의 존재 가능한 상태를 생각해보자. 다음과 같이 4가지 종류로 존재 가능하다. 다만 이 중 (d)는 가로로 붙어 있게 배치할 수 없다고 하였으므로 불가하여 (a)~(c)의 3가지만 이.. 2024. 2. 21. [자바] 백준 16400 - 소수 화폐 (java) 목차 문제 : boj16400 필요 알고리즘 에라토스테네스의 체, DP (동적 계획법), 냅색 (배낭 문제), 정수론 에라토스테네스의 체로 소수를 전처리 후, 냅색 DP를 돌려서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 순서대로 생각해보자. 1. N이하의 화폐를 모두 알아야 한다. -> 에라토스테네스의 체 등으로 N 이하의 모든 소수를 미리 구해두자. sqrt(N) 까지만 확인해본 이유는 '에라토스테네스의.. 2023. 12. 15. [자바] 백준 30025 - K의 배수 (java) 목차 문제 : boj30025 필요 알고리즘 DP (동적 계획법), 수학 DP를 이용해 풀 수 있는 문제이다. 풀이를 위해 수학적인 지식이 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 M자리의 양의 정수를 구하고, 그 중 K의 배수가 몇 개인지 구하는 문제이다. 물론 실제로 가능한 모든 M자리 양의 정수를 구해보면 O(N^M) = O(10^100) 이라는 천문학적인 경우의수가 되므로 불가능하다. 그럼 어떻게.. 2023. 12. 12. [자바] 백준 2418 - 단어 격자 (java) 목차 문제 : boj2418 필요 알고리즘 DP (동적 계획법) BFS 같은걸론 시간초과가 나게된다. 동적 계획법으로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 '각 칸은 중복되게 사용해도 된다.' 부분이 문제인데, 이 부분때문에 BFS나 DFS로 진행 시 중복체크를 못하므로 시간복잡도가 저 멀리 가버리게 된다. 게다가 경우의 수의 경우 최대 10^18 이라고 했으므로, 따로 시간복잡도를 계산해보지.. 2023. 12. 8. [자바] 백준 20500 - Ezreal 여눈부터 가네 ㅈㅈ(java) 목차 문제 : boj20500 필요 알고리즘 동적 계획법 (DP), 정수론 정수론 특히 나머지 연산의 성질에 대해 알아야 하고, 효율적으로 풀기 위해 DP가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아래와 같이 자리수를 늘려나가 만들어지는 N자리 양의 정수 중 15의 배수가 몇 개인지 구하는 문제이다. 당연하게도 1과 5로 이루어진 N자리 수는 2^N 개나 된다. 2^1515개의 정수는 천문학적인 수치이므로 .. 2023. 12. 5. [자바] 백준 28706 - 럭키 세븐 (java) 목차 문제 : boj28706 필요 알고리즘 DP (동적 계획법) DP로 해결 가능한 문제이다. 이하 풀이는 bit DP (비트필드를 이용한 다이나믹 프로그래밍)로 풀었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 모든 경우의 수를 본다고 해보자. 1부터 시작해서 차례차례 경우의 수를늘려가는거다. 이러면 당연히 2^200000의 경우의 수가 존재하므로 너무나 천문학적인 수치이다. 그럼 어떻게 해야할까? 이 문제에서 결과.. 2023. 11. 24. 이전 1 2 3 4 ··· 6 다음
