이 영역을 누르면 첫 페이지로 이동
Stranger's LAB 블로그의 첫 페이지로 이동

Stranger's LAB

페이지 맨 위로 올라가기

Stranger's LAB

프로그래밍과 관련하여 다양한 알고리즘 문제를 풀어보고, 프로그래밍 언어를 이해해 볼 수 있도록 돕고자 만든 블로그 입니다.

[백준] 1463번 : 1로 만들기 - JAVA [자바]

  • 2020.08.28 20:56
  • JAVA - 백준 [BAEK JOON]/동적 계획법 1
글 작성자: ST_
728x90






www.acmicpc.net/problem/1463

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

 









  • 문제




 

 

 

 

 

 

 

 

 

 

 





  • 알고리즘 [접근 방법]

 



 

 

생각보다 어렵지 않게 풀 수 있는 문제다. 이번 문제는 재귀로 풀이해볼 것이다. 크게 세 가지 경우의 수로 나눌 수 있는데, 3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우가 있다. 여기서 1로 만들기 위한 최소 연산 횟수를 찾아내야 한다.

 

여기서 함정이 하나 있다.

"무조건 큰 수로 나눈다고 해결되진 않는다."

 

위 이미지의 힌트에서 볼 수 있듯이 10을 큰 수부터 나눠보기 시작하면 10 -> 5 -> 4 -> 2 -> 1 이렇게 4번의 연산이 필요하다. 하지만 정답은 10 -> 9 -> 3 -> 1 로 3이 정답이다.

 

또한 2와 3의 배수, 즉 6으로 나눠지는 경우의 수도 있다. 그럼 코드로 짠다면 다음과 같은 경우의 수로 나눌 수 있겠다.

 

Integer[] dp; // 메모이제이션 할 배열
static int recur(int N) {

	// 탐색하지 않았던 N일 경우
	if (dp[N] == null) {
		// 6으로 나눠질 경우
		if (N % 6 == 0) {
			
		}
		// 3으로만 나눠지는 경우
		else if (N % 3 == 0) {
			
		}
		// 2로만 나눠지는 경우
		else if (N % 2 == 0) {
			
		}
		// 2와 3으로 나누어지지 않는 경우
		else {
			
		}
	}
	return dp[N];
}

 

 

그리고 각 부분에 재귀호출을 하면서 DP를 최솟값으로 갱신해주어야 한다. 이 때 앞서 말한 것 처럼 무조건 큰 수로 나누는 것이 최솟값이 아니기 때문에 이를 조심해야 한다.

 

즉, 6으로 나눠지는 경우는 3으로 나누는 경우와 2로 나누는 경우, 1을 빼는 경우 모두 재귀호출 하여 3가지 경우 중 최솟값으로 DP를 갱신해야 하고, 3으로만 나눠지는 경우는 3으로 나누는 경우와 1을 빼는 경우를 재귀호출, 2로만 나눠지는 경우는 2로 나누는 경우와 1을 빼는 경우의 수를 재귀호출, 그 외에는 1을 빼는 경우만 재귀호출을 해주면 된다.

 

그리고 각 부분에 이전 재귀호출 중 최솟값에 1을 더한 값이 현재 N에 대한 최소연산 횟수가 된다.

말로하면 어려울 테니 알고리즘 부분만 떼어서 코드를 작성하면 다음과 같다.

 

[알고리즘1]

Integer[] dp; // 메모이제이션 할 배열

static int recur(int N) {

	if (dp[N] == null) {
		// 6으로 나눠지는 경우 
		if (N % 6 == 0) {
			dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
		}
		// 3으로만 나눠지는 경우 
		else if (N % 3 == 0) {
			dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
		}
		// 2로만 나눠지는 경우 
		else if (N % 2 == 0) {
			dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
		}
		// 2와 3으로 나누어지지 않는 경우
		else {
			dp[N] = recur(N - 1) + 1;
		}
	}
	return dp[N];
}

 

 

이렇게 짜면 알고리즘이 완성된다.

 

 

 

물론 dp를 사용하지 않는 방법도 있다. 아예 재귀 호출 할 때 같이 연산 횟수를 같이 갱신시키는 것이다. 그렇게 해서 N=1 이 되기 전 까지 count를 누적했다가 1이 되면 누적된 count를 반환하여 재귀를 탈출시키는 것이다.

 

코드로 예로들어 보자면 이렇다.

 

[알고리즘 2]

static int recur(int N, int count) {
	if (N < 2) {
		return count;
	}
    
	/*
	 N으로 각각 2와 3으로 나누면 count는 +1에 각 연산의
	 나머지 값을 더해준 것이 된다.
	 나머지 값은 빼기 1했을 때의 count 값과 같기 때문
	*/
	return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));

}

 

예로들어 N이 5라고 할 때, 5 -> 4 -> 2 -> 1 로 총 3이 된다.

위 수식의 원리로 보자면 이렇다. recur(N/2, count + 1 + (N % 2)) 를 보자면 이렇게 된다.

N = 5, count = 0

N = 5 / 2 = 2, count = 0 + 1 + 1(나머지값)

N = 2 / 2 = 1, count = 2 + 1 + 0(나머지 값)

N = 1 이므로 return count -> 3이 반환

이런식으로 되는 것이다.

 

물론 그 옆의 recur(recur(N / 3, count + 1 + (N % 3)) 도 있으니 정확하게 말하자면 이렇게 된다.

 

recur(5,0)

min( recur(2,2) , recur(1, 3) )

min( min( recur(1, 3) , recur(0,5) ) , min( recur(0, 3), recur(0, 5) ) )

min( min( 3 , 5 ) , min( 3, 5 ) )

min( 3, 3 )

output : 3

 

 

이런식으로 해줄 수도 있다. 아마 DP를 따로 갱신하지 않고 count만 누적해주면서 나눗셈과 나머지만 필요로 하므로 실제로는 알고리즘2 코드가 좀 더 효율이 좋을 것이다. 그럼 두 가지 경우를 모두 짜주었으니 본격적으로 코드를 보도록 하자.

 

 

 

 

 

 

 

 

 





  • 4가지 방법을 사용하여 풀이한다.

 



위 알고리즘 설명에서 보여드렸던 두 가지 방식을 토대로 각 알고리즘별 입력방법을 바꾸어 성능을 비교해보고자 한다.

 

1 . Scanner + 알고리즘 1

2. BufferedReader + 알고리즘 1

3 . Scanner + 알고리즘 2

4. BufferedReader + 알고리즘 2

 

 

 

 






  • 풀이





- 방법 1 : [Scanner + 알고리즘 1]

 

import java.util.Scanner;
public class Main {

	static Integer[] dp;

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		dp = new Integer[N + 1];
		dp[0] = dp[1] = 0;

		System.out.print(recur(N));

	}

	static int recur(int N) {

		if (dp[N] == null) {
			// 6으로 나눠지는 경우 
			if (N % 6 == 0) {
				dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
			}
			// 3으로만 나눠지는 경우 
			else if (N % 3 == 0) {
				dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
			}
			// 2로만 나눠지는 경우 
			else if (N % 2 == 0) {
				dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
			}
			// 2와 3으로 나누어지지 않는 경우
			else {
				dp[N] = recur(N - 1) + 1;
			}
		}
		return dp[N];
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다. 아마 틀린이유야 다양하겠지만, 재귀로 풀 때 위와같은 경우의 수를 안나눠서 틀렸던 분들도 분명 많을 것 같다.

 

 











- 방법 2 : [BufferedReader + 알고리즘 1]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	static Integer[] dp;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		dp = new Integer[N + 1];
		dp[0] = dp[1] = 0;

		System.out.print(recur(N));

	}

	static int recur(int N) {

		if (dp[N] == null) {
			// 6으로 나눠지는 경우 
			if (N % 6 == 0) {
				dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
			}
			// 3으로만 나눠지는 경우 
			else if (N % 3 == 0) {
				dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
			}
			// 2로만 나눠지는 경우 
			else if (N % 2 == 0) {
				dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
			}
			// 2와 3으로 나누어지지 않는 경우
			else {
				dp[N] = recur(N - 1) + 1;
			}
		}
		return dp[N];
	}

}

 

 

 

 

 

 











- 방법 3 : [Scanner + 알고리즘 2]

 

 

 

알고리즘 1의 경우 DP를 갱신해주면서 이모이제이션을 했다. 그렇다보니 N-1 즉, 1을 뺀 값도 재귀호출을 해줬어야 했지만, 알고리즘 2 방법은 그럴 필요 없이 나머지 값을 이용하여 count를 갱신해주는 방법이기 때문에 좀 더 효율이 좋을 것이다.

 

 

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(recur(N, 0));
	}

	static int recur(int N, int count) {
		// N이 2 미만인 경우 누적된 count값을 반환
		if (N < 2) {
			return count;
		}
		return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));

	}
}

 

 

 

아마 수식을 본다면 크게 어렵지 않게 이해했을 것이다. 오히려 코드가 매우 간결해진 것 같다.

 

 

 











- 방법 4 : [BufferedReader + 알고리즘 2]

 

 

 

입력방법만 바뀌었을 뿐 별다른 변경점은 없다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
		System.out.println(recur(N, 0));
	}
 
	static int recur(int N, int count) {
		// N이 2 미만인 경우 누적된 count값을 반환
		if (N < 2) {
			return count;
		}
		return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));
 
	}
}

 

 

 

 

 

 

 

 

 

 

 





  • 성능






 

채점 번호 : 22116348  -  방법 4 : BufferedReader + 알고리즘 2

채점 번호 : 22116341  -  방법 3 : Scanner + 알고리즘 2

채점 번호 : 22116330  -  방법 2 : BufferedReader + 알고리즘 1

채점 번호 : 22116325  -  방법 1 : Scanner + 알고리즘 1

 

 

위 결과에서 볼 수 있듯 알고리즘에 따라 메모리와 시간차이가 많이 난다. 또한 입력의 경우 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

 

 

 








  • 정리

 



 

오늘은 간단하게 문제를 풀어낼 수 있었다. 다른 몇몇의 재귀로 풀이하시는 분을 봤는데, 초기에 아예 처음부터 모든 곳을 방문하여 값을 저장한 뒤 이후 3과 2로 나누어 최솟값을 찾는 분들도 있었다. 하지만 그러면 3000ms대를 찍을 정도로 비효율적이기 때문에 추천하는 방법은 아니다.

 

그러니 일단 스스로 고민을 해본 뒤 모르는 부분에서 검색을 해보시거나 하면 좋을 것 같다.

혹여 모르는 부분이 있다면 댓글 달아주시는대로 빠르게 답변드리도록 하겠다.

 

 

 



저작자표시 비영리 변경금지 (새창열림)

'JAVA - 백준 [BAEK JOON] > 동적 계획법 1' 카테고리의 다른 글

[백준] 2156번 : 포도주 시식 - JAVA [자바]  (21) 2020.08.31
[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]  (46) 2020.08.29
[백준] 2579번 : 계단 오르기 - JAVA [자바]  (35) 2020.08.27
[백준] 1932번 : 정수 삼각형 - JAVA [자바]  (17) 2020.08.26
[백준] 1149번 : RGB거리 - JAVA[자바]  (18) 2020.08.11

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [백준] 2156번 : 포도주 시식 - JAVA [자바]

    [백준] 2156번 : 포도주 시식 - JAVA [자바]

    2020.08.31
  • [백준] 10844번 : 쉬운 계단 수 - JAVA [자바]

    [백준] 10844번 : 쉬운 계단 수 - JAVA [자바]

    2020.08.29
  • [백준] 2579번 : 계단 오르기 - JAVA [자바]

    [백준] 2579번 : 계단 오르기 - JAVA [자바]

    2020.08.27
  • [백준] 1932번 : 정수 삼각형 - JAVA [자바]

    [백준] 1932번 : 정수 삼각형 - JAVA [자바]

    2020.08.26
다른 글 더 둘러보기

정보

Stranger's LAB 블로그의 첫 페이지로 이동

Stranger's LAB

  • Stranger's LAB의 첫 페이지로 이동

검색

나의 외부 링크

  • st-github

공지사항

  • 공지 - 블로그 사용 설명서

메뉴

  • 홈
  • 방명록

카테고리

  • 전체 카테고리 (267)
    • Java (5)
    • JAVA - 백준 [BAEK JOON] (177)
      • 입출력과 사칙연산 (14)
      • 조건문 (7)
      • 반복문 (11)
      • 1차원 배열 (7)
      • 함수 (3)
      • 문자열 (10)
      • 기본 수학 1 (8)
      • 기본 수학 2 (6)
      • 2차원 배열 (0)
      • 정렬 (10)
      • 재귀 (4)
      • 브루트 포스 (5)
      • 집합과 맵 (0)
      • 기하 1 (5)
      • 정수론 및 조합론 (12)
      • 백트래킹 (8)
      • 동적 계획법 1 (15)
      • 누적 합 (0)
      • 그리디 알고리즘 (5)
      • 스택 (5)
      • 큐, 덱 (7)
      • 분할 정복 (9)
      • 이분 탐색 (7)
      • 기타 문제 (17)
      • 별 찍기 문제 모음 (2)
    • C++ - 백준 [BAEK JOON] (46)
      • 입출력과 사칙연산 (14)
      • 조건문 (7)
      • 반복문 (11)
      • 1차원 배열 (7)
      • 함수 (3)
      • 문자열 (0)
      • 기타 문제 (4)
    • 자료구조 (18)
      • Java (18)
    • 알고리즘 (11)
      • Java (11)
    • 프로그래밍 기초 (6)
    • 이모저모 (2)
    • 일상의 글 (2)

최근 글

정보

ST_의 Stranger's LAB

Stranger's LAB

ST_

블로그 구독하기

  • 구독하기
  • 네이버 이웃 맺기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © ST_.

티스토리툴바