Dazzling 개발 노트

[백준] 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의 배수가 아니니 조건을 타지..

[백준] 9655 - 돌 게임 (Java) 문제 https://www.acmicpc.net/problem/9655 풀이/후기 다이나믹 프로그래밍 연습을 위해 선택한 문제인데, 점화식을 찾기 위해 패턴을 찾다가 홀수이면 SK, 짝수이면 SY인 점을 찾았다. 그래서 한 번 홀수, 짝수로 구현해 보니 바로 정답이 나왔다. DP니까 DP로 풀면 어떻게 되는지도 같이 확인했다. (결국엔 동일함) 코드 package DynamicProgramming; import java.io.*; public class Problem9655 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new I..

문제 N가지 종류의 화폐가 있다. 화폐의 개수를 최소한으로 이용해 그 가치의 합이 N원이 되도록 하려고 한다. 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 1

[백준] 1463 - 1로 만들기 (Java) 문제 https://www.acmicpc.net/problem/1463 풀이/후기 이코테에서 풀었던 1로 만들기와 거의 똑같은 문제였다. 차이점은 5 연산식이 없다는 것. 문제 복습을 위해 점화식을 직접 만들어봤는데, 몇 시간 전에 비슷한 문제를 풀었는데도 한 번에 잘 떠오르지 않았다. 복습이 중요할 것 같다...^^ https://da-zzling.tistory.com/35 코드 package DynamicProgramming; import java.io.*; public class Problem1463 { static int[] d = new int[1000000+1]; public static void main(String[] args) throws I..

문제 https://www.acmicpc.net/problem/11727 풀이/후기 이코테에서 풀었던 바닥 공사 문제와 완전히 동일하다 https://da-zzling.tistory.com/37 코드 package DynamicProgramming; import java.io.*; public class Problem11727 { static int[] d = new int[1000 + 1]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); d..

[백준] 11726 - 2 x N 타일링 (Java) 문제 https://www.acmicpc.net/problem/11726 풀이/후기 이코테에서 DP 유형의 문제를 풀다가, 타일링 문제가 대표적인 유형이라길래 백준에서 비슷한 문제를 풀어봄 총 3가지 경우가 나온다고 생각했는데, 1x2타일이 3번과 같은 경우가 되어 결국 2가지 경우가 나옴 이 부분은 유튜브 풀이 보고 알게된 점인데 역시 글로 여러번 읽는 것보다 영상으로 강의한번씩 듣는게 효과가 큰 것 같다@ 코드 package DynamicProgramming; import java.io.*; public class Problem11726 { static int[] d = new int[1000+1]; public static void main(St..

문제 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있음 이 얇은 바닥을 1 * 2덮개, 2 * 1덮개, 2 * 2덮개 세 가지의 덮개를 이용하여 채우고자 함 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성 예를 들어 2*3 크기의 바닥을 채우는 경우의 수는 5 * 출력 시 바닥을 채우는 방법의 수를 796796으로 나눈 나머지를 출력 (입력예시) 3 (출력예시) 5 풀이/후기 (다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라고 하는데, 단지 결과값이 굉장히 커질 수 있기 때문임) 다이나믹 프로그래밍의 기초 예제에서 필수적인 타일링 문제 유형임 코드 package ThisIsCT; import java.io.BufferedReader; impo..