Dev.baelanche
[백준 1915] 가장 큰 정사각형
작년에 카카오 모의테스트에서 이와 똑같은 문제가 나온적이 있었다. 당시에 dp 문제를 하나도 풀 줄 몰랐는데 신기하게도 이건 술술 풀렸다;; 1. 입력받은 대로 2차원 배열을 채운다. 2. 정사각형의 조건을 만족하려면 가로, 세로의 길이가 같고 인접한 배열을 모두 1이어야 하므로 좌측 위, 좌측, 위의 값이 모두 1 이상이어야 한다. 3. 메모이제이션 기법으로 큰 정사각형의 크기를 누적시키며 진행한다. a[i][j] = min(a[i-1][j-1], a[i-1][j], a[i][j-1]) + 1; 2번을 풀어쓰면 위 식과 같겠다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = ..
[백준 2903] 중앙 이동 알고리즘
점의 개수가 9, 25, 81 ... 순으로 늘어난다. 위 수는 1 + (2^1), 1 + (2^2), 1 + (2^3) 으로 바꿔줄 수 있다. 따라서 1 + (2^n) 이 점의 개수이다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long dot = 1 + (long)Math.pow(2, n); System.out.println(dot * dot); } }
[백준 1057] 토너먼트
토너머트 참가 인원, 김지민의 번호, 임한수의 번호를 매 반복마다 반으로 줄여준다. 홀수 일때는 +1을 해줘야한다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a = sc.nextInt(); int b = sc.nextInt(); int i; boolean m = false; for(i=1; n>=2; i++) { int arr[] = new int[n+1]; arr[a] = 1; arr[b] = 1; for(int start=1; start
[백준 10815] 숫자 카드
매 케이스마다 상근이의 카드 한개를 비교할 카드 배열의 길이를 반으로 쪼개며 이분탐색한다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; for(int i=0; i0) { int card = sc.nextInt(); int left = 0; int right = n-1; while(left + 1 < right) { int mid = (left + right)/2; if(a[mid]
[백준 1009] 분산처리
컴퓨터를 10개씩 짜른다. 0번째 컴퓨터의 경우 10으로 출력하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0) { int a = sc.nextInt(); int b = sc.nextInt(); int c = a % 10; for(int i=0; i
[백준 2979] 트럭 주차
도착시간과 떠난시간 사이의 트럭 개수를 출력하여 맞는 요금을 부여하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); int truck[][] = new int[3][2]; for(int i=0; i truck[2][1]) break; } System.out.println(cost); } }
[백준 1547] 공
야바위를 할때마다 자리를 스왑해주면된다. 공이 사라지는 경우는 없다;;;; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int a[] = new int[4]; a[1] = 1; while(m-->0) { int x = sc.nextInt(); int y = sc.nextInt(); swap(a, x, y); } for(int i=1; i
[백준 14500] 테트로미노
N*M 배열에서 테트로미노를 놓을 수 있는 경우를 모두 체크한다. 코드를 보면 구현방식을 아주 쉽게 알 수 있다. public class Main { static int a[][]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); a = new int[n][m]; ..