알고리즘

백준 11052번 카드 구매하기 [ Java ]

11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net N번째 카드의 최대 조합을 구하기 위해선 1부터 N-1까지의 카드팩 조합 + N-1번째 카드팩의 갯수랑 N번째 카드팩의 개수를 비교해서 큰 걸로 골라야합니다. O(n^2) import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStr..

백준 9095번 1, 2, 3 더하기 [ Java ]

9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net n을 만들기 위해 A(n) = A(n-1) + A(n-2) + A(n-3)의 점화식을 사용하면 구할 수 있다. import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int[] memo = new int[11]; int T = Integer.p..

백준 11727번 2×n 타일링 2 [ Java ]

11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2×n 타일링 1번에서 1개의 경우만 추가 되었습니다. A(n) = A(n-1) + A(n-2) + A(n-2) import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] memo = new int[1001]; int n = Integer...

백준 2089번 -2진수 [ Java ]

2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuild..

백준 17087번 숨바꼭질 6 [ Java ]

17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net gcd를 이용하는 문제였습니다. 수빈이가 있는 위치와 각 동생들의 거리들의 최대공약수를 구하는 문제였습니다. import java.io.*; import java.util.*; public class Main { static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } public static void main(String[] args) throws I..

백준 2745번 진법 변환 [ Java ]

2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 뒷 자리 문자부터 해당 진법으로 변환해 더해주는 계산을 하였습니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringT..

백준 11005번 진법 변환 2 [ Java ]

11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 중학교 때 이진법 변환을 할때 ㄴ을 그리면서 2로 나누는 연산처럼 해당 진수로 나누면서 StringBuilder 앞에다가 추가해주면서 뒤로 보냈습니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamRe..

백준 17103번 골드바흐 파티션 [ Java ]

17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 이전에 풀었던 골드바흐 코드를 조그만 수정하면 풀 수 있다. import java.io.*; import java.util.*; public class Main { static StringBuilder sb = new StringBuilder(); static boolean isPrime[] = new boolean[1000001]; public static void main(String[] args) throws IOException { BufferedReader..

백준 1212번 8진수 2진수 [ Java ]

1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); String[] firstOct = {"0", "1", "10", "11", "100", "101", "110", "111"}; String[] oct = {"..

백준 1373번 2진수 8진수 [ Java ]

1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 재귀를 사용해서 맨 뒷자리부터 처리하는 방법밖에 생각나지 않았었는데 앞 부분부터 변환할 수 있다는 것을 배웠습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); char[] str = br.readLi..