7주차_백준 문제풀이
목차
1. 문제 1463
2. 문제 10870
3. 문제 2108
1. 문제 1463
풀이
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
static int d[];
public static void main(String[] args) throws Exception
{
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
d = new int[N+1];
d[1] = 0;
for (int i = 2; i < N+1; i++)
{
d[i] = d[i-1]+1;
if (i % 2 == 0 && d[i] > d[i/2]+1) //i가 2로 나눠질때
{
d[i] = d[i/2]+1;
}
if (i % 3 == 0 && d[i] > d[i/3]+1) //i가 3로 나눠질때
{
d[i] = d[i/3]+1;
}
}
System.out.println(d[N]);
// N까지의 연산횟수 출력
// System.out.println(Arrays.toString(d));
}
}기본설명
정수 X에 사용할 수 있는 연산은 세가지입니다.
① 1을 뺀다. -> X가 어떤 수이든지 1을 뺄 수 있다.
② X가 2로 나누어 떨어지면, 2로 나눈다.
③ X가 3으로 나누어 떨어지면 3으로 나눈다.
실제 문제와 다르게 알아보기 쉽게 하기 위하여 1번은 1 빼기, 2번은 2로 나누기, 3번은 3으로 나누기로 재정리하였습니다.
정수 N이 주어졌을 때, 세 가지 연산을 적절히 사용해서 1을 만들 때 연산을 사용하는 횟수의 최소값을 출력해야 합니다.
i가 10일 때 2로 나누어서 나머지가 0이 되므로 가능한 연산은 ① 1 빼기와 ② 2 나누기입니다.
그러면 연산횟수는 2개 연산에 대해서 계산해보겠습니다.
아래 그림에서와 같이 ①번 연산은 i-1=10-1=9 연산횟수에서 1을 더합니다. d[10] = d[9] + 1 = 3
②번 연산은 i/2=10/2=5 연산횟수에서 1을 더합니다. d[10] = d[5] + 1 = 4
두 연산 중 ①번 연산이 더 작으므로 d[10] = 3이 됩니다.
d[10] 값이 3이므로 10이 1로 될 때까지 진행하는 연산은 3번입니다.
위에서 풀은 걸 10부터 1까지 작은 수가 되는 경우를 찾아보면
10 -> 9(1 빼기) -> 3(3 나누기) -> 1 (3 나누기)로 이동하는 것을 알 수 있습니다.
무식하게 하나씩 해보았지만 법칙이 보인다는 걸 알 수 있습니다.
최소 연산횟수를 저장하면 다시 계산할 필요가 없습니다. (메모이제이션)
- 1를 뺄 때는 d[i] = d[i-1] + 1
- 2로 나눌 수 있을 때는 d[i] = d[i/2] + 1
- 3으로 나눌 수 있을 때는 d[i] = d[i/3] + 1
소스로 구현하실 때 초기값인 d[1] = 0을 꼭 해줘야합니다.
2. 문제 10870
풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
System.out.println(fibonacci(N));
}
// 피보나치 함수
static int fibonacci(int N) {
if (N == 0) return 0;
if (N == 1) return 1;
return fibonacci(N - 1) + fibonacci(N - 2);
}
}기본설명
위와같이 Fibonacci 함수 안에서 또 Fibonacci 함수를 호출하는 식으로 재귀를 하는 것이다.
그리고 재귀를 하다가 N = 1 이거나, N = 0 이면 더이상 함수를 호출하지 않고 return 시키면서 가장 안쪽 재귀부터 하나씩 값을 더해 return 해주는 방식이다.
3. 문제 2108
풀이
// [백준] 2108. 통계학 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
int[] arr = new int[n]; // 숫자 저장할 배열
int a = 0; // 산술평균
int b = 0; // 중앙값
int c = 0; // 최빈값
int d = 0; // 범위
// 숫자 입력
for(int i=0;i<n;i++) {
arr[i] = Integer.parseInt(in.readLine());
}
// 산술평균
int sum = 0;
for(int i=0;i<n;i++) {
sum += arr[i];
}
a = (int)Math.round(((double)sum /n));
// 중앙값
Arrays.sort(arr);
b = arr[n/2];
// 최빈값
int[] plus = new int[4002];
int[] minus = new int[4001];
for(int i=0;i<n;i++) {
// 0 ~ 4000 빈도 저장
if(arr[i] <0) {
minus[Math.abs(arr[i])]++;
}
// -1 ~ -4000 빈도 저장(배열은 마이너스가 없기 때문에 따로 저장!)
else {
plus[arr[i]]++;
}
}
ArrayList<Integer> list = new ArrayList<>();
// 가장 높은 빈도수 체크
int max = 0;
for(int i=0; i<plus.length;i++) {
max = Math.max(max, plus[i]);
}
for(int i=0; i<minus.length;i++) {
max = Math.max(max, minus[i]);
}
// 가장 빈도 높은 숫자들 따로 ArrayList에 담기
for(int i : arr) {
if(i<0) {
if(minus[Math.abs(i)] == max && !(list.contains(i))) {
list.add(i);
}
}
else {
if(plus[i] == max && !(list.contains(i))) {
list.add(i);
}
}
}
// 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다!
// 2개 이상이면 2번째로 작은 것 출력
if(list.size()>=2) {
c = list.get(1);
}
// 1개면 그대로
else {
c = list.get(0);
}
// 범위는 최대에서 최소값을 뺀 것
d = arr[n-1] - arr[0];
System.out.println(a);
System.out.println(b);
System.out.println(c);
System.out.println(d);
in.close();
}
}코드설명
우선 산술 평균은 문제에 나온대로 N개의 수의 합을 N으로 나눈 값의 반올림을 구하면 되고,
중앙값은 N은 홀수라고 주어졌으므로 정렬 후 n/2 위치의 값을 구하면 된다.
범위도 위에서 정렬했으니 인덱스 0 값, 마지막 인덱스 값을 빼면된다.
빈도수를 체크하는 방법은 Counting Sort, 카운팅 정렬을 이용한다.
카운팅 정렬의 기본 메커니즘은 데이터의 값이 몇 번 나왔는지를 세주는 것이다. 말 그대로 counting 하는 것이다.
우선, 배열은 마이너스가 없기 때문에 나누어서 plus 배열에는 0 ~ 4000을 저장해주고
minus 배열에는 -1 ~ -4000을 저장해준다.
그 후 배열을 순회하여 가장 높은 빈도수를 체크한다.
이제 빈도 높은 숫자들을 따로 ArrayList에 담고,
그 숫자가 2개 이상이라면 두번째로 작은 값을 출력해야 하므로 2번째 인덱스 값 (정렬되어있으므로),
1개라면 그냥 처음인덱스 값이 최빈값이다.