Problem Solved/BOJ

[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..

[BOJ][Java] 2747번 - 피보나치 수

문제 백준 2747번 문제: 피보나치 수 피보나치 수 시리즈 문제 풀이 2747번. 피보나치 수 1 2748번. 피보나치 수 2 2749번. 피보나치 수 3 10826번. 피보나치 수 4 10870번. 피보나치 수 5 문제 설명 동적 계획법으로 피보나치 수를 계산하는 문제 n이 45까지 주어진다. 최대 45까지이므로 배열을 만들 때 int형으로 만들어도 숫자 저장이 가능하다. 1번째와 2번째 값, 즉 n의 값이 0이나 1일 때는 초기값인 0과 1을 반환해야 한다. n이 2 이상일 경우에는 피보나치의 식Fn = Fn-1 + Fn-2을 따라 배열에 저장해 주면 된다. 처음에는 재귀함수로 풀려고 시도했지만 시간 초과가 떠서 재귀로는 풀지 못했다. 성공 코드 import java.io.BufferedReader..

[BOJ][Java] 9663번 - N-Queen

문제 백준 9663번 문제: N-Queen 문제 설명 한줄에 하나의 Queen만 존재 가능하므로 1차원 배열 선언 N+1크기의 배열을 선언한 후 재귀로 경우의 수를 구한다. int array는 선언 시 0으로 초기화되므로 배열 요소가 1부터 시작하도록 한다. array를 0부터 채웠을 때 문제점은 아래의 표를 보면 알 수 있다. 0으로 시작했을 때 디버깅한 것을 보면 값이 중복되어 들어간다. arr[i] == arr[row] 조건에 걸려 false가 리턴되었기 때문이다. 조건 1. 같은 열에 있거나 조건 2. 대각선에 위치할 경우를 제외하고 찾는다. 대각선에 위치하기 위한 조건 (기준 x좌표 값 - 대각선 x좌표값)의 절대값 == (기준 y좌표 값 - 대각선 y좌표값)의 절대값 x의 좌표값끼리의 절대값과..