백준

백준 1010번 다리놓기 [ Java ]

서쪽과 동쪽의 사이트를 연결하는 경우의 수를 구하기 위해선 사이트의 수가 더 많은 곳을 기준으로 잡아야 합니다. 문제에서의 예시로 보면 서쪽엔 4개 동쪽엔 7개의 사이트가 있는데 동쪽의 7개의 사이트 중에 4개를 뽑아야 하니 7C4의 연산이 나옵니다. 조합(Combination)의 연산을 하기 위해 조합의 특징중의 하나인 파스칼의 삼각형을 이용합니다. 파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전 nCr = (n-1)C(r-1) + (n-1)Cr 이므로 이걸 함수로 구현하면 아래와 같이 표현할 수 있습니다. int combination(int n, int r) { if (r == 0 || n == r) return 1; return memo[n][r] = combination(n-1, r-1) + ..

백준 15661번 링크와 스타트 [ Java ]

15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 재귀로 나올 수 있는 모든 가지수를 만들어내서 isStart에 표시를 하고 start팀과 start표시가 없는 link팀을 뽑아 합산한 후 비교합니다 import java.io.*; import java.util.*; public class Main { static int N; static int M; static int[][] player; static boolean[] isStart; static int result..

백준 1476번 날짜 계산 [ Java ]

1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 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)); String input = br.readLine(); int E = 0, S = 0, M =..

백준 11728번 배열 합치기 [ Java ]

11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 우선순위 큐 Priority Queue를 이용하여 입력받는 동시에 정렬을 해서 출력하였습니다. 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..

백준 2525번 오븐 시계 [ Java ]

2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int hour = sc.nextInt(); int minute = sc.nextInt() + sc.nextInt(); while (minute > 59) { hour++; minute -= 60; } while (hour > 23..

백준 10797번 10부제 [ Java ]

10797번: 10부제 서울시는 6월 1일부터 교통 혼잡을 막기 위해서 자동차 10부제를 시행한다. 자동차 10부제는 자동차 번호의 일의 자리 숫자와 날짜의 일의 자리 숫자가 일치하면 해당 자동차의 운행을 금지하는 www.acmicpc.net 입력을 배열로 받고 그 배열을 filter로 걸러서 길이를 확인합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new ..

백준 1915번 가장 큰 정사각형 [ Java ]

1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 현재 위치가 1인지 확인하고 1이라면 왼쪽, 위, 왼쪽위 내용들을 검사해서 모두 0이 아니면 최소값 + 1 을 해서 한변의 길이를 구합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[][] map; public static void main(Strin..

백준 9465번 스티커 [ Java ]

9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net n번째 스티커를 뜯지 않았을 경우 1번째 줄을 뜯었을 경우 2번째 줄을 뜯었을 경우의 최댓값을 비교한다. 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)); Str..

백준 2225번 합분해 [ Java ]

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 123더하기에 범위가 추가되었습니다. 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)); StringTokenizer st = new StringTokenizer(br.readLine()); long mod = 1000000000L; int N = Integer.parseInt(st.nextToken(..

백준 1699번 제곱수의 합 [ Java ]

1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net D[N]을 모두 1로 채웠을때가 최대기 때문에 D[i] = i(최대값)으로 하고 min 연산을 한다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..