목록알고리즘 (266)
Dev.baelanche
[백준 9012] 괄호
스택 관련 문제이다. 스택에 '(' 기호가 들어오면 모두 push하고, ')' 기호가 들어오면 스택의 top이 '(' 일때 push 한다. 입력이 끝났을때 스택이 비어있으면 VPS 조건이 성립한다. public class Main { Node head; int size = 0; class Node { Node prev; Object value; Node(Object value) { this.value = value; } } public void push(Object value) { Node node = new Node(value); if(size >= 1) node.prev = head; head = node; size++; } public Object pop() { if(size == 0) { retu..
[백준 10828] 스택
스택으로 입출력하면 되는 간단한 문제이다. 본 문제에서는 직접 구현한 스택으로 풀었다. import java.util.Scanner; public class Main { Node head; int size = 0; class Node { Node prev; Object value; Node(Object value) { this.value = value; } } public void push(Object value) { Node node = new Node(value); if(size >= 1) node.prev = head; head = node; size++; } public Object pop() { if(size == 0) { return -1; } Node temp = head; head = he..
[백준 11727] 2xn 타일링 2
경우의 수를 구해보면 f(n) = 2(fn-2) + (f-1) 이다. 동적계획법으로 풀면 된다. public static int[] dp; public static int f(int n) { if(n == 0) {dp[0] = 0; return 0;} if(n == 1) {dp[1] = 1; return 1;} if(n == 2) {dp[2] = 3; return 3;} if(n == 3) {dp[3] = 5; return 5;} if(dp[n] != -1) return dp[n]; int result = 2*(f(n-2)%10007) + f(n-1)%10007; dp[n] = result; return result; } public static void main(String[] args) { Scann..
[백준 11726] 2xn 타일링
n의 증가에 따른 방법의 수를 구해보면 피보나치 수열이다. public static int dp[]; public static int f(int n) { if(n == 0) {dp[0] = 0; return 0;} if(n == 1) {dp[1] = 1; return 1;} if(n == 2) {dp[2] = 2; return 2;} if(dp[n] != -1) return dp[n]; int result = f(n-2)%10007 + f(n-1)%10007; dp[n] = result; return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = ..
[백준 1904] 01타일
n 의 길이에 따라 만들 수 있는 이진수열의 수를 구해보면 피보나치 수열과 같다. 1. 동적계획법을 이용하여 배열을 채운다. 2. (A+B)%M = (A%M+B%M)%M 을 이용한다. public static int f(int n) { if(n == 0) {dp[0] = 0; return 0;} if(n == 1) {dp[1] = 1; return 1;} if(n == 2) {dp[2] = 2; return 2;} if(dp[n] != -1) return dp[n]; int result = f(n-2)%15746 + f(n-1)%15746; dp[n] = result; return result; } public static void main(String[] args) { Scanner sc = new S..
[백준 2193] 이친수
n자리 이친수의 개수를 세어보면 피보나치 수열이란 것을 알 수 있다. 1. n의 범위가 90 까지이므로 자료형을 long 으로 선언해야 한다. public static long pinary(int n) { if(n == 0) {dp[0] = 0; return 0;} if(n == 1) {dp[1] = 1; return 1;} if(dp[n] != -1) return dp[n]; long result = pinary(n-2) + pinary(n-1); dp[n] = result; return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new lo..
[백준 15873] 공백 없는 A+B
나누기를 이용한 규칙으로 풀려다가 이 시간에 dp 문제 푸는게 나을 것 같아서 그냥 막 풀었다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); String num = sc.next(); int length = num.length(); int sum = 0; if(length == 2) sum = num.charAt(0) + num.charAt(1) - 96; else if(length == 3) { if(num.charAt(1) == '0') sum = num.charAt(2) - 38; else sum = num.charAt(0) - 38; } else sum = 20; sc.close(); System.out..
