Java 알고리즘 스터디 - DP, 그리디

1003 피보나치 함수

📌문제 링크

https://www.acmicpc.net/problem/1003

📋코드

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

public class Main {
	static int[][] dp = new int[41][2];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
        
        // 초기값 설정 : 0은 0을 한 번 호출하고, 1은 1을 한 번 호출한다
        // 첫 번째 인덱스는 N번째 피보나치 수
        // 두 번째 인덱스 [0] : 0을 호출한 횟수, [1] : 1을 호출한 횟수
		dp[0][0] = 1;
		dp[1][1] = 1;
		
        // 피보나치 수에서 0과 1을 호출한 횟수 각각 구하기
		for (int i = 2; i < 41; i++) {
			dp[i][0] = dp[i-1][0] + dp[i-2][0];
			dp[i][1] = dp[i-1][1] + dp[i-2][1];
		}
		
		int N;
		for (int i = 0; i < T; i++) {
			N = Integer.parseInt(br.readLine());
			sb.append(dp[N][0]).append(" ").append(dp[N][1]).append("\n");
			
		}
		
		System.out.print(sb);
	}

}

10844 쉬운 계단 수

📌문제 링크

https://www.acmicpc.net/problem/10844

💡 문제 풀이

이 블로그를 참고했습니다..
https://code-lab1.tistory.com/108

📋코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long mod = 1000000000;
		long[][] dp = new long[N+1][10];
		
		// 첫 번째 자릿수 (왼쪽에서 첫 번째)는 경우의 수가 하나뿐임 (숫자를 지정해줌)
		for (int i = 1; i < 10; i++) {
			dp[1][i] = 1;
		}
		
		// 두 번째 자릿수부터 N번째 자리수까지 탐색
		for (int i = 2; i < N+1; i++) {
			// 현재 자리값을 0부터 9까지 탐색
			for (int j = 0; j < 10; j++) {
				// 현재 자릿수 9라면 이전 자릿수는 8만 가능
				if (j == 9) {
					dp[i][9] = dp[i-1][8] % mod;
				}
				// 현재 자릿수가 0이라면 이전 자릿수는 1만 가능
				else if (j==0) {
					dp[i][0] = dp[i-1][1] % mod;
				}
				// 그 외는 1씩 차이나는 숫자 가능
				else {
					dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
				}
			}
		}
		
		long ans = 0;
		for (int i = 0; i < 10; i++) {
			ans += dp[N][i];
		}
		
		System.out.println(ans%mod);
	}

}

11727 2xn 타일링 2

📌문제 링크

https://www.acmicpc.net/problem/11727

💡 문제 풀이

다음 블로그를 참고했습니다..
https://jaemin8852.tistory.com/158

📋코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int mod = 10007;
		
        // N이 1일땐 1 출력 후 종료
		if (N == 1) {
			System.out.println(1);
			return;
		}
		
        // 인덱스는 가로 길이
		int[] dp = new int[N+1];
        // 가로 길이가 1일 때 타일링할 수 있는 경우의 수는 1
		dp[1] = 1;
        // 가로 길이가 2일 때 타일링할 수 있는 경우의 수 : 3
		dp[2] = 3;
		
        //
		for (int i = 3; i <= N; i++) {
			dp[i] = (dp[i-2] * 2 + dp[i-1]) % mod;
		}
		
		System.out.println(dp[N]);
	}

}

20015 에너지 드링크

📌문제 링크

https://www.acmicpc.net/problem/20115

💡 문제 풀이

📋코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		
		int N = Integer.parseInt(br.readLine());
		
        // 큰 수부터 pop하도록 comparator 설정
		PriorityQueue<Double> queue = new PriorityQueue<>(new Comparator<Double>() {

			@Override
			public int compare(Double o1, Double o2) {
				// TODO Auto-generated method stub
				return Double.compare(o2, o1);
			}
		});
        
        // 입력받은 수 queue에 넣음
		stk = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			queue.offer(Double.parseDouble(stk.nextToken()));
		}
		
		double a, b;
        
        // 에너지 드링크의 수가 1개만 남을 때까지 반복
		while(queue.size() > 1) {
        	// 양이 많은 건 건드리지 않고 양이 적은 에너지 드링크를 흘림
			a = queue.poll();
			b = queue.poll();
			a += b/2;
			queue.offer(a);
		}
		
		System.out.println(queue.poll());
	}

}

1213 팰린드롬 만들기

📌문제 링크

https://www.acmicpc.net/problem/1213

📋코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		char[] str = sc.nextLine().toCharArray();
		int[] alphabet = new int[26];
		
        // 알파벳 개수 저장
		for (char c : str) {
			alphabet[c-'A'] += 1;
		}
		
		int cnt = 0;
        
        // 개수가 홀수인 문자를 찾음
        // 홀수인 문자가 하나라면 그 숫자를 가운데로
		int center = -1;
		for (int i = 0; i < 26; i++) {
			if (alphabet[i] % 2 == 1) {
				cnt++;
				center = i;
			}
			
		}
		
        // 개수가 홀수인 문자가 2개 이상이라면 팰린드롬 만들기 불가
		if (cnt > 1) {
			System.out.println("I'm Sorry Hansoo");
			return;
		}
		
        // 알파벳 순서대로 개수의 절반만큼 append
		for (int i = 0; i < 26; i++) {
			if (alphabet[i] > 1) {
				for (int j = 0; j < alphabet[i]/2; j++) {
					sb.append((char)(i+'A'));
				}
			}
		}
		
        // 팰린드롬 처음 절반
		System.out.print(sb);
        // 가운데 글자
		if (center > -1)
			System.out.print((char)(center + 'A'));
        // 나머지 절반 거꾸로 출력
		System.out.println(sb.reverse());
	}

}