Problem Solved

[BOJ][Java] 1932번 - 정수 삼각형

문제 백준 1932번 문제: 정수 삼각형 문제 설명 각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제 최대값을 찾기 위해서는 이전 열에서 최대값을 더해 나가야 한다. 문제의 예제로 이해를 해보자 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5맨 위의 수인 7은 제일 상단에 위치해 3과 8에 각각 7을 더해주면 된다. 그럼 10과 15가 되어 밑의 수들에게 선택을 받게 된다. 하지만 셋째줄의 맨 처음에 있는 8과 0은 선택의 여지가 없이 위의 수를 더해야 한다. 1은 10과 15 중 큰 수인 15를 선택할 수 있다. 이를 이용하여 큰 수를 축적해 나갈 수 있다. 아래 축적된 수를 보자. 7 10 15 18 16 15 20 25 20 19 24 30 27 26 24가장 밑에 줄에 가장..

[BOJ][Java] 1149번 - RGB거리

문제 백준 1149번 문제: RGB거리 문제 설명 i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다. 설명 추가 예정 성공 코드 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); int[][] rgb = new int[3][n+1]; for (int i = 0; i < n; i++){ rgb[0][i] = s.nextInt(); rgb[1][i] = s.nextInt(); rgb[2][i] = s.nextInt(); } for (int i = 1; i..

[BOJ][Java] 9461번 - 파도반 수열

문제 백준 9461번 문제 : 파도반 수열 문제 설명 피보나치 수와 비슷한 규칙을 찾아 동적 계획법으로 푸는 문제 파도반 수열은 n에서 두번째 수와 세번째 수를 더하면 n의 값이 나오는 문제이다. 재귀로 풀면 시간 초과로 틀린다. 배열에 차곡차곡 담는 식으로 풀어야 한다. 초기값은 처음 3개의 값인 1로 두면 된다. 성공 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for (int i = 0; i < t; i++) { int n = sc.nextInt(); System.out.print..

[BOJ][Java] 1904번 - 01타일

문제 백준 1904번 문제: 01타일 문제 설명 n의 증가로 타일 개수를 세어 봤을 때의 표이다. * n = 11* n = 22* n = 33* n = 45* n = 58* n = 613* n = 721* n = 834* n = 955* n = 1089* n = 11144* n = 12233* n = 13377* n = 14610 n = n-1 + n-2 구조를 띠고 있다. 앞에서 풀었던 피보나치 수와 비슷하게 풀면 된다. 단, 주의할 것은 15746을 나눈 나머지 값으로 저장하면서 for문을 돌아야 한다는 것이다. 성공 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = ..

[BOJ][Java] 1003번 - 피보나치 함수

문제 백준 1003번 문제: 피보나치 함수 문제 설명 단순 재귀로 피보나치 수를 구하면 왜 느릴까요? 함수 호출의 개수가 기하급수적으로 늘어나기 때문입니다. N번째 피보나치 수에서 0이 출력되는 횟수와 1이 출력되는 횟수를 구하는 문제 아래는 각 n마다 0과 1의 출력 횟수를 작성한 것이다. fibo(0) --- 0이 1번 1이 0번 fibo(1) --- 0이 0번 1이 1번 fibo(2) --- 0이 1번 1이 1번 fibo(3) --- 0이 1번 1이 2번 fibo(4) --- 0이 2번 1이 3번 fibo(5) --- 0이 3번 1이 5번 fibo(6) --- 0이 5번 1이 8번 fibo(7) --- 0이 8번 1번 13번 fibo(8) --- 0이 13번 1이 21번 fibo(n)의 1의 횟수 ..

[BOJ][Java] 2748번 - 피보나치 수 2

문제 [백준 2748번 문제: 피보나치 수 2](https://www.acmicpc.net/problem/2748) 피보나치 수 시리즈 문제 풀이 2747번. 피보나치 수 1 2748번. 피보나치 수 2 2749번. 피보나치 수 3 10826번. 피보나치 수 4 10870번. 피보나치 수 5 문제 설명 피보나치 수를 동적 계획법으로 구하는 문제 피보나치 수 1번 문제와 동일한 문제이다. 다른 점은 n이 45에서 90으로 증가했다는 점이다. 이 때문에 수를 저장하는 배열이 long 형태여야 한다. 성공 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputSt..