Dazzling 개발 노트

[백준] 1699 - 제곱수의 합 (Java) 문제 https://www.acmicpc.net/problem/1699 풀이/후기 일단 필요한 제곱수를 미리 계산해서 num배열에 넣어주었다. num = {1,4,9,...} 처음에 생각한 점화식(오답) dp[i] = Math.min(i / num[j] + i % num[j], dp[i]); 점화식을 찾아낸 것에 뿌듯해하고 있었는데, 13에서 예외 상황이 발생했다. 내 점화식대로 하면 4 + 4 + 4 + 1 그러나 13은 9 + 4로 바로 표현될 수 있다. 제곱수끼리의 합으로 표현되는 경우인데 원래 점화식에서 이 부분만 수정을 해줄까 했으나 결국 점화식이 틀려서 발생된 상황이라 새로운 접근법을 생각해야 했다. dp[i] = Math.min(dp[i - nu..

[백준] 1699 - 제곱수의 합 (Java) 문제 https://www.acmicpc.net/problem/1699 풀이/후기 일단 필요한 제곱수를 미리 계산해서 num배열에 넣어주었다. num = {1,4,9,...} 처음에 생각한 점화식(오답) dp[i] = Math.min(i / num[j] + i % num[j], dp[i]); 점화식을 찾아낸 것에 뿌듯해하고 있었는데, 13에서 예외 상황이 발생했다. 내 점화식대로 하면 4 + 4 + 4 + 1 그러나 13은 9 + 4로 바로 표현될 수 있다. 제곱수끼리의 합으로 표현되는 경우인데 원래 점화식에서 이 부분만 수정을 해줄까 했으나 결국 점화식이 틀려서 발생된 상황이라 새로운 접근법을 생각해야 했다. dp[i] = Math.min(dp[i - nu..

[백준] 2225 - 합분해 (Java) 문제 https://www.acmicpc.net/problem/2225 풀이/후기 dp 구조는 dp[x][y]일 때, x개를 이용하여 합이 y인 결과를 얻는 것으로 두고 짜면 된다. 점화식은 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];를 이용하여 풀이한다. 2차원 표로 생각해보면, 구하고자 하는 칸의 바로 왼쪽과 바로 윗쪽 칸의 값을 더하면 원하는 결과를 얻을 수 있다. DP는 점화식만 만들면 쉽게 풀 수 있는데, 점화식을 만드는 것이 너무 어렵다!ㅠㅠㅠㅠㅠ 애초에 dp를 어떤 구조로 생각할지도 감이 잡히지 않아서 결국 검색을 해보았다. 세상엔,, 똑똑한 사람이 참 많고 난 작게 느껴진다,,ㅠㅠ 계속 반복하면서 복습해야겠다..! 코드 p..

[백준] 1325 - 효율적인 해킹 (Java) 문제 https://www.acmicpc.net/problem/1325 풀이/후기 지금까지 dfs/bfs 문제는 항상 2차원배열[][]을 이용해서 풀었는데, 이번 문제는 배열을 이용하니 메모리 초과가 발생했다. 그래서 arrayList를 이용하여 풀었다. 배열, arrayList, LinkedList를 적절한 때에 잘 사용하는 것이 필요한 것 같다. 그 이후에는 일반적인 dfs, bfs 풀듯이 풀이하면 되는데, 이번엔 이차원배열의 형태가 아니라서 for문을 이용해 list 내부를 탐색하는 반복문을 사용하면 된다. 출력은 결과값이 가장 큰 값이 여러개일 수 있어 result 배열에 각 컴퓨터별 해킹 가능 최대개수를 저장해둬야한다. 마지막에 max를 찾아 ma..

[백준] 1654 - 렌선 자르기(Java) 문제 https://www.acmicpc.net/problem/1654 풀이/후기 나무 자르기 문제와 비슷하지만 조금 더 쉽게 풀었다. 렌선의 길이가 커서 double과 BigInteger까지 생각했는데 그냥 long으로 풀면 되는거였다. mid가 0인 경우 나누는 수가 0이되어 오류가 발생하는데, start를 0이 아닌 1로 잡아주니 바로 해결되었다. 코드 package BinarySearch; import java.io.*; import java.util.*; public class Problem1654 { static int K, N; static long[] arr; public static void main(String[] args) throws IO..

[백준] 2805 - 나무 자르기 (Java) 문제 https://www.acmicpc.net/problem/2805 풀이/후기 이코테 책에서 푼 문제와 유사해서 복습 느낌으로 금방 끝날 줄 알았는데, 삽질하는데 시간을 엄청 투자했다,,, - 일단 처음 오답이 나온 부분은 long처리였다. 나무의 합 sum 은 long형태로 사용해야 한다. 이거 외에 별다른 오답 부분이 없는데 왜 자꾸 오답처리가 되는지 한참 고민했다. 결국 찾아낸 부분은 처음 start와 end 설정 부분이었는데, 내가 배열을 정렬한 후 arr[0] 과 arr[N-1]로 지정한 부분이 문제였다. 이렇게 지정하면 배열의 값이 하나인 경우 start와 end가 잘 작동하지 않게 된다. 그리고 내 처음 생각으론 start가 가장 짧은 막대 ..

[백준] 10815 - 숫자 카드(Java) 문제 https://www.acmicpc.net/problem/10815 풀이/후기 수 범위도 정수 범위 내여서 그냥 이진탐색 구현해주면 가볍게 풀 수 있다. 이제 이정도는 가볍게 풀 수 있나보다,,^^; 코드 package BinarySearch; import java.io.*; import java.util.*; public class Problem10815 { static int N, M; static int[] arrN; static int[] arrM; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStream..

[백준] 14501 - 퇴사 (Java) 문제 https://www.acmicpc.net/problem/14501 풀이/후기 5월에 브루트포스 문제 풀다가 만난 문제로 그때 당시 DP 풀이를 보고나서 도망갔던 문제를 다시 풀어보았다. 이제는 DP가 익숙하지만 점화식을 세우는 것은 여전히 어려웠다... 이미 나와있는 점화식을 보고도 이해하는데 한참 걸리니,,^^; 아직도 갈 길이 멀다 싶다 ㅋㅋ 그래도 계속 보다보니 이해가 가긴 한다! 이게 어디야,, dp[t[i] + i] = Math.max(dp[t[i] + i] , dp[i] + p[i]); 그리고 작업을 진행하지 못한 날은 0이 아니라 그 전에 최대값으로 채워줌 dp[i+1] = Math.max(dp[i], dp[i+1]); 코드 import jav..