Do it! 알고리즘 코딩 테스트(83번 ~ 84번)

83번 선물 전달

---

내가 떠올린 풀이 해설

완전 순열이라는 개념을 사용하는 문제이다. 완전 순열은 n개의 원소의 집합에서 원소들을 재배열할 때 이전과 같은 위치에 배치되는 원소가 1개도 없을 때를 말한다. arr[n] 배열의 의미를 n명일 때 선물을 교환할 수 있는 모든 경우의 수로 정한다. n명이 존재한다고 가정하고 A와 B라는 학생에게 선물을 줬다고 가정하자 이때는 교환 방식이 2가지가 존재한다.

선물을 교환하는 2가지 방식

1. B도 A에게 선물을 줬을 때 : N명 중 2명이 교환을 완료했으므로 남은 경우의 수는 arr[n - 2]
2. B는 A가 아닌 다른 친구에게 선물을 전달할 때 : N명 중 B만 받은 선물이 정해진 상태이므로 남은 학생은 N - 1이며 경우의 수는 arr[n - 1]이다

A는 자기 자신이 아닌 N - 1명에게 선물을 전달 할 수 있다. 이 과정으로 경우의 수를 구하는 점화식은 arr[N] = (N - 1) * (arr[N - 2] + arr[N - 1]) 

---

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek1947 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long mod = 1000000000;
		long[] arr = new long[1000001];
		arr[1] = 0;
		arr[2] = 1;
		for(int i = 3; i <= n; i++) {
			arr[i] = (i - 1) * (arr[i - 2] + arr[i - 1]) % mod;
		}
		System.out.println(arr[n]);
	}
}

---

84번 1로 만들기

---

내가 떠올린 풀이 해설

사용할 수 있는 3가지 연산을 바텀-업 방식으로 구현할 수 있는지 연습하는 문제이다. 

1. 점화식 형태와 의미를 도출한다. 

arr[i] : i 에서 1로 만드는 데 걸리는 최소 연산 횟수

2. 점화식을 구한다.

arr[i] = arr[i - 1] + 1 // 1을 빼는 연산이 가능함
if(i % 2 == 0) arr[i] = min(arr[i], arr[i / 2] + 1) // 2로 나누는 연산이 가능함
if(i % 3 == 0) arr[i] = min(arr[i], arr[i / 3] + 1) // 3으로 나누는 연산이 가능함

3. 점화식을 이용해 arr배열을 채운다.

4. arr[n] 을 출력한다.

---

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek1463 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int cnt = 0;
		int[] arr = new int[n + 1];
		arr[1] = 0;
	
		for(int i = 2; i <= n; i++) {
			arr[i] = arr[i - 1] + 1;
			if(i % 2 == 0) {
				arr[i] = Math.min(arr[i], arr[i / 2] + 1);
			}
			if(i % 3 == 0) {
				arr[i] = Math.min(arr[i], arr[i / 3] + 1);
			}
		}
		System.out.println(arr[n]);
	}
}

---

오늘의 회고

오늘은 조합 1문제와 DP문제를 풀었습니다. 점화식 세우는 방법이 너무 어렵습니다.. 지금까지 혼자 잘 공부해왔지만 불안한 감도 있어서 프로그래머스에서 [커뮤러닝/6기] 코딩 테스트 실력 UP 강의를 자부담비 10%와 내일배움카드가 90%를 지원해준다고 해서 신청하게 되었습니다. 선발된 과정에 충실하게 공부해서 실력을 한층 더 높이는 계기가 되었으면 좋겠습니다. 하반기에 원하는 기업에 입사하고 싶습니다.