Dazzling 개발 노트

[백준] 1912 - 연속합 (Java) 문제 https://www.acmicpc.net/problem/1912 풀이/후기 DP 문제를 계속해서 풀면서 정말 오랜만에 자력으로 점화식을 도출해냈다. 아주 자신감있게 풀어서 주어진 예제가 모두 맞게 나오는 것을 확인하고 제출하니 오답이 나왔다. dp[i] = Math.max(dp[i-1], arr[i-1]) + arr[i]; 이 점화식에선 무조건 두 개 이상의 숫자를 선택한 경우이다. 연속된 몇 개의 수를 선택하는 경우 외에 하나의 수만 선택할 수도 있으므로 arr[i]는 꼭 더해져야 하는 부분이 아니다. dp[i] = Math.max(dp[i-1] + arr[i], arr[i]); 이렇게 수정하니 정답처리가 되었다. 정말 오랜만에 자신있게 풀었는데,, 마무..

[백준] 11053 - 가장 긴 증가하는 부분 수열 (Java) 문제 https://www.acmicpc.net/problem/11053 풀이/후기 처음에는 문제를 잘못읽고 풀어서 오답이 나왔다. 그리고 dp에 수열 중 선택한 값을 저장하는 방식으로 풀었는데 생각해보니까 수열의 크기를 구해야하기 때문에 dp에 부분 수열의 번호를 넣어서 풀어야 했다. 마지막에 dp[N-1]을 출력하면 당연히 답이 나와야한다고 생각했는데 N-1번째 숫자가 부분 수열의 멤버가 아닐 수 있기 때문에 그렇게 하면 안된다. 반복문을 한 번 더 돌려서 dp의 가장 큰 값을 뽑아서 출력한다. 코드 package DynamicProgramming; import java.io.*; import java.util.*; public clas..

[백준] 2579 - 계단 오르기 (Java) 문제 https://www.acmicpc.net/problem/2579 풀이/후기 점화식을 얻어내려고 정말 열심히 찾았는데,, 결국 못찾았다ㅠㅠㅠ 검색해서 점화식 확인해보니 조금만 더 생각했으면 도출할 수 있을 것 같기도 하고,, 살짝 아쉽다 코드 package DynamicProgramming; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Problem2579 { public static void main(String[] args) throws IOException { BufferedReader br = new B..

[백준] 2407 - 조합 (Java) 문제 https://www.acmicpc.net/problem/2407 풀이/후기 BigInteger 연산 주의!! 확률과 통계 이슈로 순열과 조합부터 복습이 필요했다..^^; 여기서 nPr은 반복문을 돌며 N-i을 곱하는 것으로 표현하고 r!은 i+1을 곱하는 것으로 표현 반복문을 마치면 그 결과를 나눠주면 됨 (다이나믹프로그래밍으로 풀기) 파스칼의 삼각형을 이용하여 풀이할 수 있다. 이차원 배열을 이용하여 파스칼 삼각형을 표현한다. 코드 package DynamicProgramming; import java.io.*; import java.util.*; import java.math.BigInteger; public class Problem2407 { stati..

[백준] 9095 - 1,2,3 더하기 (Java) 문제 https://www.acmicpc.net/problem/9095 풀이/후기 이번 문제는 점화식을 쉽게 찾아낼 수 있는 문제였는데 집중력이 부족한건지,, 잘 생각이 안난다 ㅠㅠ 다이나믹프로그래밍은 점화식을 찾아내는게 가장 키 포인트라 그런지 수학 문제가 많이 나온다 나,, 수학 이렇게 재능 없던가? 코드 package DynamicProgramming; import java.io.*; public class Problem9095 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(S..

[백준] 17626 - Four Squares (Java) 문제 https://www.acmicpc.net/problem/17626 풀이/후기 다들 패턴을 찾느라 오래걸렸다고 하는데 난 스스로 찾기는 커녕 이해하는데도 오래 걸렸다,,ㅋㅋ dp[1] = 1 dp[2] = dp[1] + 1 = 2 dp[3] = dp[2] + 1 = 3 dp[4] = 1 dp[5] = dp[2^2] + dp[1] = 2 dp[6] = dp[2^2] + dp[2] = 3 dp[7] = dp[2^2] + dp[3] = 4 dp[8] = dp[2^2] + dp[2^2] = 2 숫자 i는 자신의 제곱수(dp[j*j])들을 기준으로 제곱수를 뺀 나머지 값의 합을 구하면 된다. → 따라서 점화식은 dp[i] = dp[i- j*j] + ..

[백준] 17143 - 낚시왕 (Java) 문제 https://www.acmicpc.net/problem/17143 풀이/후기 문제를 읽을 때는 좀 혼란스러웠지만 풀어보니 생각보다 엄청 어렵지는 않았다. 처음 입력을 받을 때 데이터를 어떤식으로 가지고 있을까 고민이 많았는데 sharkinfo라는 1차원 배열을 이용해 0에는 속력, 1에는 이동방향, 2에는 크기 이런식으로 생각하여 저장했다. (사실 이런 문제 나오면 입력 어떻게 받을지부터 한참을 고민하던 나였는데... 이렇게 바로 생각해낼 수 있어서 얼마나 뿌듯한지...!ㅎ) 그다음엔 문제에서 나온대로 차근차근 코드를 짰다. 어부가 map의 가장 오른쪽까지 이동하면 종료되고 이동할 때 가장 가까운 열의 상어를 잡은 후 상어가 이동하는 함수를 호출해주면 된..

[백준] 2839 - 설탕배달 (Java) 문제 https://www.acmicpc.net/problem/2839 풀이/후기 dp로 풀기 위해 점화식을 고민하여 풀었는데 오답이 나왔다. if (i % 3 == 0) { d[i] = d[3] * i/3; } if (i % 5 == 0) { d[i] = Math.min(d[i], d[5] * i/5); } if ((i-3) % 5 == 0) { d[i] = d[i-3] + 1; } if ((i-5) % 3 == 0) { d[i] = d[i-5] + 1; } 테스트케이스 입력 시에도 다 정답이고 내 이론상 틀린게 없었는데 검색을 해보니 이런 표가 있었다 하나씩 비교를 해보니까 16에서 걸렸다. 내가 푼대로 하면 16은 5를 빼도 3의 배수가 아니니 조건을 타지..