자바칩
[프로그래머스 / Java] 코딩테스트 연습: N으로 표현 (DP) 본문
난이도: Level 3
문제: https://school.programmers.co.kr/learn/courses/30/lessons/42895
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
DP는 자신이 없는 유형인데 이 문제는 특히나도 어려웠다.
다른 사람의 풀이를 봤는데도 이해하는 시간이 한참이나 걸렸다.
어떻게 그런 기가막힌 생각을 하는 것인지 참 신기하다.
DFS, BFS, 백트래킹처럼 알고리즘을 잘 적용시키면 풀 수 있는 문제와는 달리, 그리디나 DP는 처음부터 끝까지 본인이 이끌어낸 사고력을 요구하니까 참 어려운 것 같다.
이 문제는 숫자들을 어떻게 조합시킬 지 생각을 해야 한다.
조합시킬 수 있는 방법은 다음과 같다.
참고로 여기서 나오는 말은 다음과 같다.
2번 통에 들어갈 수 있는 숫자 = 숫자 N 2개로 가지고 만들 수 있는 숫자
1번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
= 1번 통에 들어갈 수 있는 숫자 + 1번 통에 들어갈 수 있는 숫자
= 1번 통에 들어갈 수 있는 숫자 - 1번 통에 들어갈 수 있는 숫자
= 1번 통에 들어갈 수 있는 숫자 * 1번 통에 들어갈 수 있는 숫자
= 1번 통에 들어갈 수 있는 숫자 / 1번 통에 들어갈 수 있는 숫자
조합 방법
2번 통에 들어갈 수 있는 숫자
= 1번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
3번 통에 들어갈 수 있는 숫자
= 1번 통에 들어갈 수 있는 숫자 (+ - * /) 2번 통에 들어갈 수 있는 숫자
= 2번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
4번 통에 들어갈 수 있는 숫자
= 1번 통에 들어갈 수 있는 숫자 (+ - * /) 3번 통에 들어갈 수 있는 숫자
= 2번 통에 들어갈 수 있는 숫자 (+ - * /) 2번 통에 들어갈 수 있는 숫자
= 3번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
...
8번 통에 들어갈 수 있는 숫자
= 1번 통에 들어갈 수 있는 숫자 (+ - * /) 7번 통에 들어갈 수 있는 숫자
= 2번 통에 들어갈 수 있는 숫자 (+ - * /) 6번 통에 들어갈 수 있는 숫자
= 3번 통에 들어갈 수 있는 숫자 (+ - * /) 5번 통에 들어갈 수 있는 숫자
= 4번 통에 들어갈 수 있는 숫자 (+ - * /) 4번 통에 들어갈 수 있는 숫자
= 5번 통에 들어갈 수 있는 숫자 (+ - * /) 3번 통에 들어갈 수 있는 숫자
= 6번 통에 들어갈 수 있는 숫자 (+ - * /) 2번 통에 들어갈 수 있는 숫자
= 7번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
i번 통에 들어갈 수 있는 숫자
= j번 통에 들어갈 수 있는 숫자 (+ - * /) i - j번 통에 들어갈 수 있는 숫자
규칙이 바로 보일 것이다.
그렇다면 이제 코드를 하나씩 보자.
우선 전역에서 사용할 변수로 Set 배열을 선언한다.
N 사용 횟수의 최솟값이 8보다 크면 -1을 return 하라는 조건이 있으므로, 인덱스를 8까지만 사용하도록 배열 크기를 9로 초기화한다.
매개변수로 받은 N과 number가 같다면 1을 리턴한다.
왜냐하면 만약 N = 5, number = 5라면, 5는 단 1개만으로도 5를 만들 수 있으므로 N 사용횟수의 최솟값은 무조건 1이 된다.
참고로 이 아래부터도 모두 solution 메서드 안에 있는 코드이다.
우선 dp[1] ~ dp[8]이 모두 HashSet을 가질 수 있도록 초기화를 해준다.
숫자 N 1개로는 조합을 할 수가 없이 N만 만들 수 있으므로, 1번 통에 들어갈 수 있는 숫자는 N밖에 없다.
for문으로 숫자 N을 2개부터 8개까지 사용할 때의 경우의 수를 찾자.
참고로 숫자 5를 2개 사용해서 만들 수 있는 숫자에는 55도 포함된다.
숫자 5를 3개 사용하면 555, 숫자 5를 4개 사용하면 5555도 포함된다는 뜻이다.
StringBuilder를 선언하고, 숫자 N을 연속 i번 반복해서 추가하고 i번째 통에 StringBuilder를 Integer로 형변환해서 넣는다.
왜 dp[j]와 dp[i - j]를 반복시키는지 좀 더 알기 쉽게 하기 위해, 위에서 설명한 부분을 주석에 그대로 써 놓았다.
i번 통에 들어갈 수 있는 숫자들을 j번 통에 들어있는 숫자와 i - j번 통에 들어있는 있는 숫자들의 사칙연산으로 모두 조합한 뒤, i번 통에 들어있는 숫자들 중에서 number가 있다면 N을 i번 사용한 횟수가 가장 최솟값이므로 i를 리턴한다.
왜냐하면 for문으로 점점 커질 것이기 때문이다.
만약 for문으로 i를 2부터 8까지 돌렸는데도 number를 조합할 수 없다면, N을 2번에서 8번 사용했을 때에는 number를 만들 수가 없으므로 -1을 리턴한다.
전체코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
import java.util.*;
class Solution {
// N 사용 횟수는 8까지만 허용하므로
// 인덱스를 1 ~ 8까지 사용하기 위해 크기를 9로 지정
Set<Integer>[] dp = new HashSet[9]; // dp 집합 배열
public int solution(int N, int number) {
if (N == number) { // 숫자 N이 목표 숫자 number와 같다면
return 1; // N 사용횟수의 최솟값 1 리턴
}
// dp 인덱스(1 ~ 8)가 모두 HashSet을 가질 수 있도록 초기화
for (int i = 1; i <= 8; i++) {
dp[i] = new HashSet<>();
}
// 숫자 N 1개로는 N만 만들 수 있음
// 1번 통에 들어갈 수 있는 숫자는 N밖에 없음
dp[1].add(N);
// 숫자 N을 2부터 8까지 사용할 때의 경우의 수 찾기
// => i(2 ~ 8)번 통에 들어갈 수 있는 숫자들을 모두 찾기
for (int i = 2; i <= 8; i++) {
// N이 연속 i번 반복되는 숫자를 만들기 위한 StringBuilder
// 선언하자마자 N을 StringBuilder에 1번 추가
StringBuilder sb = new StringBuilder().append(N);
// N을 StringBuilder에 i - 1번 더 추가
for (int j = 1; j < i; j++) {
sb.append(N);
}
// N이 연속 i번 반복되는 StringBuilder를 Integer로 변환해서 i번 통에 추가
dp[i].add(Integer.parseInt(sb.toString()));
// 2번 통에 들어갈 수 있는 숫자
// = 1번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
// 3번 통에 들어갈 수 있는 숫자
// = 1번 통에 들어갈 수 있는 숫자 (+ - * /) 2번 통에 들어갈 수 있는 숫자
// = 2번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
// 4번 통에 들어갈 수 있는 숫자
// = 1번 통에 들어갈 수 있는 숫자 (+ - * /) 3번 통에 들어갈 수 있는 숫자
// = 2번 통에 들어갈 수 있는 숫자 (+ - * /) 2번 통에 들어갈 수 있는 숫자
// = 3번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
// ...
// 8번 통에 들어갈 수 있는 숫자
// = 1번 통에 들어갈 수 있는 숫자 (+ - * /) 7번 통에 들어갈 수 있는 숫자
// = 2번 통에 들어갈 수 있는 숫자 (+ - * /) 6번 통에 들어갈 수 있는 숫자
// = 3번 통에 들어갈 수 있는 숫자 (+ - * /) 5번 통에 들어갈 수 있는 숫자
// = 4번 통에 들어갈 수 있는 숫자 (+ - * /) 4번 통에 들어갈 수 있는 숫자
// = 5번 통에 들어갈 수 있는 숫자 (+ - * /) 3번 통에 들어갈 수 있는 숫자
// = 6번 통에 들어갈 수 있는 숫자 (+ - * /) 2번 통에 들어갈 수 있는 숫자
// = 7번 통에 들어갈 수 있는 숫자 (+ - * /) 1번 통에 들어갈 수 있는 숫자
// i번 통에 들어갈 수 있는 숫자
// = j번 통에 들어갈 수 있는 숫자 (+ - * /) i - j번 통에 들어갈 수 있는 숫자
// i와 j가 같은 경우를 제외한 모든 경우의 수 찾기
for (int j = 1; j < i; j++) {
for (int num1 : dp[j]) { // j번 통에 들어갈 수 있는 숫자
for (int num2 : dp[i - j]) { // i - j번 통에 들어갈 수 있는 숫자
// j번 통에 들어갈 수 있는 숫자 + (i - j)번 통에 들어갈 수 있는 숫자
dp[i].add(num1 + num2);
// j번 통에 들어갈 수 있는 숫자 - (i - j)번 통에 들어갈 수 있는 숫자
dp[i].add(num1 - num2);
// j번 통에 들어갈 수 있는 숫자 * (i - j)번 통에 들어갈 수 있는 숫자
dp[i].add(num1 * num2);
// j번 통에 들어갈 수 있는 숫자 / (i - j)번 통에 들어갈 수 있는 숫자
if (num1 != 0 && num2 != 0) { // 분자와 분모 둘다 0이 아닐 때만 나누기
dp[i].add(num1 / num2);
}
}
}
}
// i번 통에 들어갈 수 있는 숫자들 중에 number가 있다면
if (dp[i].contains(number)) {
return i; // N 사용횟수의 최솟값 i 리턴
}
}
return -1; // N 사용횟수의 최솟값이 8보다 크면 -1 리턴
}
}
|
cs |
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스 / Java] 코딩테스트 연습: 입국심사 (이분탐색) (0) | 2024.08.31 |
|---|---|
| [프로그래머스 / Java] 코딩테스트 연습: 조이스틱 (그리디) (0) | 2024.08.30 |
| [프로그래머스 / Java] 코딩테스트 연습: 모음사전 (완전탐색) (2) | 2024.08.28 |
| [프로그래머스 / Java] 코딩테스트 연습: 전력망을 둘로 나누기 (완전탐색) (2) | 2024.08.28 |
| [프로그래머스 / Java] 코딩테스트 연습: 피로도 (완전탐색) (0) | 2024.08.26 |
