[백준] 1, 2, 3 더하기 2 (!) (12101번 JAVA)
[백준] 1, 2, 3 더하기 2 (!) (12101번 JAVA)
[접근방법]
정수 n을 1,2,3의 합으로 나타내는 방법 중 사전 순으로 k 번째 오는 식을 구하는 프로그램을 작성해야 한다.
따라서, 식은 ArrayList 을 String 타입으로 선언하여 사용한다.
ArrayList<String> arr 로 선언 할때,
arr[ i - 1 ] 에 있는 수식에 "+ 1"을 붙여준다.
arr[ i - 2 ] 에 있는 수식에 "+ 2"을 붙여준다.
arr[ i - 3 ] 에 있는 수식에 "+ 3"을 붙여준다.
[JAVA 코드]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
ArrayList<String>[] arr = new ArrayList[n + 3];
// 배열 초기화
for(int i=0; i<=n+2; i++){
arr[i] = new ArrayList<>();
}
// 초기값 입력
arr[1].add("1");
arr[2].add("1+1");
arr[2].add("2");
arr[3].add("1+1+1");
arr[3].add("1+2");
arr[3].add("2+1");
arr[3].add("3");
for(int i=4; i<=n; i++){
/*
arr[i-1]에 "+1"을,
arr[i-2]에 "+2"를,
arr[i-3]에 "+3"을 붙힘
*/
for(int j=1; j<=3; j++){
for(String s : arr[i - j]){
arr[i].add(s + "+" + j);
}
}
}
// k번째 수식이 존재하지 않으면 -1 출력
if (arr[n].size() < k){
bw.write(-1 + "\n");
}
// 존재한다면, 정렬 후 k 번째 수식 출력
else {
Collections.sort(arr[n]);
bw.write(arr[n].get(k-1));
}
bw.flush();
bw.close();
}
}
** for문의 활용
향상된 for문 : 배열이나 컬렉션에 저장된 값을 매 반복마다 하나씩 읽어와서 값에 저장한다.
int[] arr = {1, 2, 3, 4, 5, 6, 7};
for(int i : arr){
System.out.println(i);
}
/*
1
2
3
4
5
6
7
*/[2회차 풀이]
[접근 방법]
1회차 풀이와 같다.
실행 시간 1초 = 약 2000만번 연산
N의 범위 (1 ≤ N < 11)
k의 범위 (1<= k <= 2^31 -1)
O(N^2) = 11 * 11 = 121 (가능)
=> 별도의 시간 복잡도 고려 X
[JAVA 코드]
// 12101 - 1, 2, 3 더하기 2
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
// 0. 입출력 선언 / 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
ArrayList<String>[] arr = new ArrayList[n+3];
// 배열 속 문자열을 생성 (초기화) - null 값을 제거
for(int i=0; i<=n+2; i++){
arr[i] = new ArrayList<>();
}
arr[1].add("1");
arr[2].add("1+1");
arr[2].add("2");
arr[3].add("1+1+1");
arr[3].add("1+2");
arr[3].add("2+1");
arr[3].add("3");
// 1. DP 방식을 사용하여 arr[n] 수식 구하기
for(int i=4; i<=n; i++){
/*
* arr[i-1]의 수식들은 "+1"을 하여, arr[i]에 저장
* arr[i-2]의 수식들은 "+2"을 하여, arr[i]에 저장
* arr[i-3]의 수식들은 "+3"을 하여, arr[i]에 저장
*/
for(int j=1; j<=3; j++){
for(String s : arr[i-j]){
arr[i].add(s + "+" + j);
}
}
}
// 2. 출력
// k번째 수식이 없는 경우
if (k > arr[n].size()){
bw.write(-1+"\n");
}
else{ // n을 이루는 k번째 수식 출력
Collections.sort(arr[n]);
bw.write(arr[n].get(k-1) + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
/*
실행 시간 1초 = 약 2000만번 연산
N의 범위 (1 ≤ N < 11)
k의 범위 (1<= k <= 2^31 -1)
O(N^2) = 11 * 11 = 121 (가능)
=> 별도의 시간 복잡도 고려 X
*/
[Rewind]
1. 어려웠던 점
- DP를 이용한 해결방안이 떠오르지 않았다.
- ArrayList를 사용한 해결방안이 떠오르지 않았다.
★ ArrayList 배열의 크기를 "n+3"으로 하는 이유를 알지 못하겠다.
(n+1로 해도 충분할 것 같은데 ArrayOutOfBounds가 발생한다.)
- ArrayList 배열을 사용할때, 각 인덱스에 위치한 ArrayList 들을 초기화 해주어야 null 값을 다루는 오류가 발생하지 않는다.
2. 알게된 점
- ArrayList의 배열을 초기화 하지 않는 경우,
위와 같은 오류가 발생한다.
java.lang.NullPointerException이 발생되는 가장 큰 원인은 Java 프로그래밍에서 사용할 객체를 생성한 후에 인스턴스를 생성하지 않은 상태에서 Null 오브젝트를 사용하려고 할 때에 발생한다.
이를 방지 하기 위해 사용 전 ArrayList 를 초기화 해야한다.
3. 개선 방안
★ ArrayList 배열의 크기를 "n+3"으로 하는 이유을 고민 해야 한다.