9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

 

  • 생각

 

fisrtInput이 i까지의 길이, secondInput이 j까지의 길이일 때, dp[i][j]가 있다.

 

1. first[i]와 second[j]가 같다면, dp[i-1][j-1]+1의 값이 dp[i][j]의 값이 될 것이다. 를 토대로 나옴

2. first[i]와 second[j]가 다르다면, first의 마지막 문자 i를 제외한 dp[i-1][j]의 경우의 수가 될 것이다. 마찬가지로 seond의 마지막 문자 j를 제외한 dp[i][j-1]의 경우의 수가 될 것이다. 여기서 우린 최장길이를 선택하는 것이니, 두 개의 경우의 수 중 큰 값을 가지고 온다. 를 토대로 나왔다.

 

https://www.youtube.com/watch?v=EAXDUxVYquY를 참고하였다.

 

  • 코드

정답 코드 : LCS 알고리즘의 점화식을 통하여 구현하였다.

 

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

public class Main {
	static int[][] dp;
	static int firstInputLength, secondInputLength;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		SetData();
		System.out.println(dp[firstInputLength][secondInputLength]);
	}
	
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String firstInput = br.readLine();
		String secondInput = br.readLine();

		firstInputLength = firstInput.length();
		secondInputLength = secondInput.length();
		dp = new int[firstInputLength + 1][secondInputLength + 1];
		
		for (int i = 1; i <= firstInputLength; i++) { 
			for (int j = 1; j <= secondInputLength; j++) { 
				if (firstInput.charAt(i - 1) == secondInput.charAt(j - 1)) { 
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else { 
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);				
				}
			}
		}
	}	
}

 

 

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 10026번 : 적록색약  (0) 2021.01.14
[BOJ/JAVA] 백준 3109번 : 빵집  (0) 2021.01.13
[BOJ/JAVA] 백준 2580번 : 스도쿠  (0) 2021.01.08
[BOJ/JAVA] 백준 2239번 : 스도쿠  (0) 2021.01.08
[BOJ/JAVA] 백준 2212번 : 센서  (0) 2021.01.07

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

 

  • 생각

백트래킹(0으로 되돌리는 작업)을 하지않고 했다가 고생좀 했다.. 0이 발견되면 1~9까지 다 넣어보면서 행, 열, 3X3 모두 체크해주면서 true가 반환되면 해당 값을 넣어준뒤 c를 +1해주면서 재귀를 돈다. 여기서 다른 값이 안될 경우가 있기 때문에 가다가 아무작업도 못하고 되돌아올 경우 다시 0으로 돌려주어야 한다.

 

  • 코드

정답 코드 : 백트래킹으로 구현한 코드이다.

 

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

public class Main {

	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		array = new int[9][9];
		sb = new StringBuilder();

		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}

		Sudoku(0, 0);

	}

	static void Sudoku(int r, int c) {

		if (c == 9) {
			sb.append("\n");
			Sudoku(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(array[i][j] + " ");
				}
				System.out.println("");
			}
			System.exit(0);
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Possible(r, c, i)) {
					array[r][c] = i;
					Sudoku(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			Sudoku(r, c + 1);
		}
	}

	static boolean Possible(int r, int c, int value) {

		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}

}

 

나중 코드 : 백트래킹으로 구현한 코드이다.

 

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

public class Main {
	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		dfs(0, 0);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		array = new int[9][9];
		sb = new StringBuilder();
		
		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}

	}

	static void dfs(int r, int c) {

		if (c == 9) {
			dfs(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(array[i][j] + " ");
				}
				sb.append("\n");
			}
			System.out.println(sb);
			System.exit(0); // 이렇게 바로 끝내줘야지 시간초과가 나지 않음
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Sudoku(r, c, i)) {
					array[r][c] = i;
					dfs(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			dfs(r, c + 1);
		}
	}

	static boolean Sudoku(int r, int c, int value) {
		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}
}

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 3109번 : 빵집  (0) 2021.01.13
[BOJ/JAVA] 백준 9251번 : LCS(Longest Common Subsequence)  (0) 2021.01.12
[BOJ/JAVA] 백준 2239번 : 스도쿠  (0) 2021.01.08
[BOJ/JAVA] 백준 2212번 : 센서  (0) 2021.01.07
[BOJ/JAVA] 백준 14226번 : 이모티콘  (0) 2021.01.07

 

2239번: 스도쿠

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다

www.acmicpc.net

 

  • 생각

백트래킹(0으로 되돌리는 작업)을 하지않고 했다가 고생좀 했다.. 0이 발견되면 1~9까지 다 넣어보면서 행, 열, 3X3 모두 체크해주면서 true가 반환되면 해당 값을 넣어준뒤 c를 +1해주면서 재귀를 돈다. 여기서 다른 값이 안될 경우가 있기 때문에 가다가 아무작업도 못하고 되돌아올 경우 다시 0으로 돌려주어야 한다.

 

  • 코드

정답 코드 : 백트래킹을 통해 구현하였다.

 

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

public class Main {

	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		array = new int[9][9];
		sb = new StringBuilder();

		for (int i = 0; i < 9; i++) {
			String s = br.readLine();
			for (int j = 0; j < 9; j++)
				array[i][j] = s.charAt(j) - '0';
		}

		Sudoku(0, 0);

	}

	static void Sudoku(int r, int c) {

		if (c == 9) {
			sb.append("\n");
			Sudoku(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(array[i][j]);
				}
				System.out.println("");
			}
			System.exit(0);
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Possible(r, c, i)) {
					array[r][c] = i;
					Sudoku(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			Sudoku(r, c + 1);
		}
	}

	static boolean Possible(int r, int c, int value) {

		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}

}

 

나중 풀이 : 백트래킹으로 구현했다.

 

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

public class Main {
	static int[][] array;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		dfs(0, 0);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		array = new int[9][9];
		sb = new StringBuilder();

		for (int i = 0; i < 9; i++) {
			String s = br.readLine();
			for (int j = 0; j < 9; j++)
				array[i][j] = s.charAt(j) - '0';
		}
	}
	
	static void dfs(int r, int c) {

		if (c == 9) {
			dfs(r + 1, 0);
			return;
		}

		if (r == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(array[i][j]);
				}
				sb.append("\n");
			}
			System.out.println(sb);
			System.exit(0);		// 이렇게 바로 끝내줘야지 시간초과가 나지 않음
		}

		if (array[r][c] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (Sudoku(r, c, i)) {
					array[r][c] = i;
					dfs(r, c + 1);
				}
				array[r][c] = 0;
			}
		} else {
			dfs(r, c + 1);
		}
	}

	static boolean Sudoku(int r, int c, int value) {
		// 행
		for (int i = 0; i < 9; i++) {
			if (array[r][i] == value) {
				return false;
			}
		}

		// 열
		for (int i = 0; i < 9; i++) {
			if (array[i][c] == value) {
				return false;
			}
		}

		// 3*3
		int tempR = (r / 3) * 3;
		int tempC = (c / 3) * 3;

		for (int i = tempR; i < tempR + 3; i++) {
			for (int j = tempC; j < tempC + 3; j++) {
				if (array[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}
}

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 9251번 : LCS(Longest Common Subsequence)  (0) 2021.01.12
[BOJ/JAVA] 백준 2580번 : 스도쿠  (0) 2021.01.08
[BOJ/JAVA] 백준 2212번 : 센서  (0) 2021.01.07
[BOJ/JAVA] 백준 14226번 : 이모티콘  (0) 2021.01.07
[BOJ/JAVA] 백준 11726 : 2 x n 타일링  (0) 2021.01.06

 

2212번: 센서

첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며

www.acmicpc.net

 

 

  • 생각

쉽게 생각하면 k개의 집중국으로 모든 센서를 커버할 수 있는 각 집중국 범위의 합을 구하는 문제이다.

 

그리디로 접근을 했다. 센서의 위치를 정렬하고 서로의 인접 거리를 계산한 뒤 기지국을 인접 거리가 긴 위치 순서대로 K개 배치하면 수신 가능 영역의 거리의 합의 최솟값을 구할 수 있게 된다.

 

 

- 예를 들어 N = 6, K = 2 일 경우

 

 

  • 코드

정답 코드 : 그리디 방식으로 풀어낸 코드이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private static int N, K, answer;
	private static int[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		N = Integer.parseInt(br.readLine());
		K = Integer.parseInt(br.readLine());
		answer = 0;
		array = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			array[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(array);

		int[] temp = new int[N - 1];
		for (int i = 0; i < N - 1; i++) {
			temp[i] = array[i + 1] - array[i];
		}
		Arrays.sort(temp);

		for (int i = 0; i < N - K; i++)
			answer += temp[i];

	}
}

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 2580번 : 스도쿠  (0) 2021.01.08
[BOJ/JAVA] 백준 2239번 : 스도쿠  (0) 2021.01.08
[BOJ/JAVA] 백준 14226번 : 이모티콘  (0) 2021.01.07
[BOJ/JAVA] 백준 11726 : 2 x n 타일링  (0) 2021.01.06
[BOJ/JAVA] 백준 11727번 : 2 x n 타일링 2  (0) 2021.01.06

 

14226번: 이모티콘

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만

www.acmicpc.net

 

  • 생각

문제를 읽었을 때, dp문제였지만 bfs 방식을 사용해도 될 것같았다. (시간안에 들어올지가 문제인데 넉넉할 것 같다고 판단함)

bfs를 사용해서 모든 경우의수로 이동해보면서 해당하는 숫자에 도달했을때 depth를 구했다.

방문 처리를 2차원배열로 해서 현재개수와 클립보드에 저장된 갯수 두가지로 체크하면서 이동했다.

 

dp방식은 잘 모르겠다..ㅜ (dp 방식으로 풀어본 사람을 찾아보려했는데 java로 푼 사람중에 dp로 푼 사람이 없었다.)

 

  • 코드

정답 코드 : bfs방식으로 구현하였다. 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	private static int S, answer;
	private static boolean[][] check;

	public static void main(String[] args) throws Exception {
		SetData();
		bfs();
		System.out.println(answer);
	}
	
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		S = Integer.parseInt(br.readLine());
		check = new boolean[1001][1001];	
		answer = 0;
	}
	
	private static void bfs() {
        Queue<int []> queue = new LinkedList<>();
        queue.offer(new int[] {1,1,1});
        check[1][1] = true;
        
        while(!queue.isEmpty()){
        	int location[] = queue.peek();
            
            if(location[0] == S){
                answer = location[2];
                break;
            }
            
            if(location[0] - 1 != 0 && !check[location[0] - 1][location[1]]){
                queue.offer(new int[] {location[0] - 1, location[1], location[2] + 1});
                check[location[0] - 1][location[1]] = true;
            }
            
            if(!check[location[0]][location[0]]){
                queue.offer(new int[] {location[0], location[0], location[2] + 1});
                check[location[0]][location[0]] = true;
            }
            
            if(location[0] + location[1] <= S && !check[location[0] + location[1]][location[1]]){
            	queue.offer(new int[] {location[0] + location[1], location[1], location[2] + 1});
                check[location[0] + location[1]][location[1]] = true;
            }
            
            queue.poll();
        }
	}
}

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 2239번 : 스도쿠  (0) 2021.01.08
[BOJ/JAVA] 백준 2212번 : 센서  (0) 2021.01.07
[BOJ/JAVA] 백준 11726 : 2 x n 타일링  (0) 2021.01.06
[BOJ/JAVA] 백준 11727번 : 2 x n 타일링 2  (0) 2021.01.06
[BOJ/JAVA] 백준 1463번 : 1로 만들기  (0) 2021.01.05

 

  • 생각

몇개의 배열을 쫙 나열하면 구현할 수 있는 수준의 점화식이였다.

배열의 결과는

1 -> 2

2 -> 2

3 -> 3
4 -> 5

5 -> 8

느낌이 오는가?? 구하고 싶은 index에서 index-1, index-2의 값을 더 해주면 된다.

 

  •  코드

  - 점화식 : i번째 index의 값은 i-1와 i-2의 index의 값 합이라는 걸 토대로 구현하였다.

 

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

public class Main {
	
	static int n;	
	static int[] dp;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		dp = new int[1001];
		
		dp[1] = 1;
		dp[2] = 2;
		
		for (int i = 3; i <1001 ; i ++) {	
			dp[i] = (dp[i-1] + dp[i-2]) % 10007;
		}
		
		System.out.println(dp[n]);
	}
}

 

 

나중에 다시 풀어본 코드 : 배열에 접근할 때 런타임 에러에만 유의하면 될 것 같다.

 

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

public class Main {
	private static int N;
	private static int[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(dp[N]);
	}
	
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		dp = new int[N + 1];
		
		dp[1] = 1;
		if(N == 1) return;
		dp[2] = 2;
		if(N == 2) return;
		for (int i = 3; i <= N; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
		}
	}
}

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 2212번 : 센서  (0) 2021.01.07
[BOJ/JAVA] 백준 14226번 : 이모티콘  (0) 2021.01.07
[BOJ/JAVA] 백준 11727번 : 2 x n 타일링 2  (0) 2021.01.06
[BOJ/JAVA] 백준 1463번 : 1로 만들기  (0) 2021.01.05
[BOJ/JAVA] 백준 17142번 : 연구소 3  (0) 2021.01.05

ㅠㅒㅓ

 

  • 생각

다이나믹프로그래밍 문제이다. 점화식의 생성 계기는 dp(N) 을 구할때 dp(N-1) + dp(N-2)에서 dp(N-2) 즉 2*(N-2)의 직사각형을 구하는 방법은 마지막에 2*2타일을 채우는 방법, 1*2 타일로 채우는 방법 2가지가 있으므로 dp(N) = dp(N-1) + dp(N-2) *2가 된다

 

  • 코드

정답 코드 : 1칸일 땐 세로로 1개, 2칸일 땐 2x2한개 2x1 두개 총 2개, N-1번의 칸에 타일 한개를 추가하는 방법과 N-2번의 칸에 2개 짜리 타일을 추가하는 방법으로 점화식을 세움.

 

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		if (N == 1) {
			System.out.println(1);
			System.exit(0);
		}
		if (N == 2) {
			System.out.println(3);
			System.exit(0);
		}
		int[] dp = new int[N + 1];
		dp[1] = 1;
		dp[2] = 3;
		for (int i = 3; i <= N; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]*2) % 10007;
		}
		System.out.println(dp[N]);
	}
}

 

다시 풀어본 코드 : N이 1, 2인 경우 반복문으로 들어가게되면 런타임이 뜨는데 해당 경우를 생각을 안해서 런타임이 한번 떴다. 또, N이 1인경우 dp[2]를 들어갈 경우 런타임이 뜬다. 

 

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

public class Main {
	private static int N;
	private static int[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(dp[N]);
	}
	
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		dp = new int[N + 1];
		
		dp[1] = 1;
		if(N == 1) return;
		dp[2] = 3;
		if(N == 2) return;
		for (int i = 3; i <= N; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]*2) % 10007;
		}
	}
}

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 14226번 : 이모티콘  (0) 2021.01.07
[BOJ/JAVA] 백준 11726 : 2 x n 타일링  (0) 2021.01.06
[BOJ/JAVA] 백준 1463번 : 1로 만들기  (0) 2021.01.05
[BOJ/JAVA] 백준 17142번 : 연구소 3  (0) 2021.01.05
[BOJ/JAVA] 백준 1339번 : 단어 수학  (0) 2021.01.04

 

 

  • 생각

알고리즘을 처음 시작할 때쯤 풀었던 문제였다. 재채점되면서 틀리게 된 문제이다.

 

질문검색에서 찾아보니 기존 코드는 아래와 같은 방법에서 오답의 결과를 냈다.

642 // 정답: 10, 오답: 11

643 // 정답: 11, 오답: 12

생각해보니 문제는 3과 2 모두가 떨어질 때 발생했다. 기존 코드는 if, if로 한것이 아닌 if, else if로 해서 6의 배수일 경우 2, 3으로 떨어지는 경우를 모두 체크를 해야했는데 그러지 못했었다.

 

  • 처음 코드
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
    	Scanner scanner = new Scanner(System.in);
        
    	int X = scanner.nextInt(); //정수 값 받아옴
    	int[] array = new int[X+1];		//배열 선언
    	
    	for(int i = 2; i<=X;i++) {
			array[i] = array[i - 1] + 1;
			if (i % 3 == 0)
				array[i] = Math.min(array[i], array[i / 3] + 1);
			else if (i % 2 == 0)
				array[i] = Math.min(array[i], array[i / 2] + 1);
    	}
    	System.out.println(array[X]);
		
	}
}

 

 

  • 나중 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int X;
	static int[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(array[X]);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		X = Integer.parseInt(br.readLine());
		array = new int[X + 1];
		
		for (int i = 2; i <= X; i++) {
			array[i] = array[i - 1] + 1;
			if (i % 2 == 0)
				array[i] = Math.min(array[i], array[i / 2] + 1);
			if (i % 3 == 0)
				array[i] = Math.min(array[i], array[i / 3] + 1);
		}
	}
}

 

 

 

- 정리

  - java 입력 받는 법

import java.util.Scanner;   //import

    	Scanner scanner = new Scanner(System.in);
	int X = scanner.nextInt(); //정수 값 받아옴

  - 최소값 가져오는 법

 Math.min(변수 1, 변수 2);

'algorithm' 카테고리의 다른 글

[BOJ/JAVA] 백준 11726 : 2 x n 타일링  (0) 2021.01.06
[BOJ/JAVA] 백준 11727번 : 2 x n 타일링 2  (0) 2021.01.06
[BOJ/JAVA] 백준 17142번 : 연구소 3  (0) 2021.01.05
[BOJ/JAVA] 백준 1339번 : 단어 수학  (0) 2021.01.04
[BOJ/JAVA] 백준 2448번 : 별찍기 - 11  (0) 2020.12.24

+ Recent posts

티스토리툴바