Dev.baelanche

줄의 개수가 최대 1000000 이라서 선택, 거품, 삽입 정렬 등의 느린 정렬방법으로는 풀 수 없다. 병합(합병) 정렬, 힙 정렬, 퀵 정렬 등으로 풀 수 있는데, 언급한 3가지 정렬 방법으로 모두 구현해 보겠다. 1. 병합 정렬(Merge Sort) public class Main { static int temp[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n; n ..

분할정복으로 * * * ***** 모양을 위, 왼쪽, 오른쪽으로 3등분하여 재귀호출하여 구현했다. public class Main { static char a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int alpha = n/3 - 1; a = new char[n][n/3*5 + alpha]; for(int i=0; i

n*n 크기의 2차원 배열을 구현하기에는 메모리가 너무 크다. 문제에서 말한대로 진행하는데는 문제가 있어 보인다. 배열을 만들지 않아도 인덱스 별로 i*j 가 들어간다는걸 이미 알고 있으므로, 루프 하나로 한 줄을 한번에 카운트 해주면 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long k = sc.nextLong(); long left = 0; long right = (long)n*n; while(left = k) right = mid - 1; else left = mid + 1; } System.out.println(lef..

문제 자체는 이분탐색으로 구현하기 쉬워보이지만 상자의 개수 * 규칙의 개수를 만들어 사용하면 메모리 초과가 난다. 별도의 구조체/클래스를 만들어 입력으로 주어지는 A, B, C 를 저장해 O(N) 으로 접근했다. 100 110 120 130 140 150 110 125 140 예제에 주어진 규칙이다. 도토리는 총 5개이니 100 -> 110 -> 110 -> 120 -> 125 순으로 진행된다. 이분탐색할 변수를 두어 3가지 분기로 구현했다. 1. 변수 mid 가 B보다 클때 (위 경우에는 B=150) - (B - A)/C + 1 = (150 - 100)/10 + 1 = 6 - 카운트에 6을 더한다. 2. min가 A보다 작을때는 스킵한다. 3. 그 외의 경우 - mid - A 가 0일때는 규칙 중 첫번..

이분탐색으로 풀었다. 1. MAXHP 로 사용할 임의 변수를 둔다. 2. Ti 에 따라 몬스터를 만나면 체력을 깎고 포션이면 체력과 공격력을 증가시킨다. 2-1. 몬스터랑 싸우는 도중 체력이 0이되면 실패하니 주의한다. 2-2. 몬스터의 체력 / 자신의 공격력이 0인지 아닌지에 따라 분기한다. 3. 반복하면서 최소의 MAXHP를 찾는다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int atk = sc.nextInt(); int a[][] = new int[n][3]; for(int i=0; i

이분 탐색으로 구현했다. 1. 임의 변수 mid 를 최대 거리로 사용했다. 2. 최대한 많은 곳에서 사용하려면 그리디한 방법으로 구현해야 한다. 2-1. 따라서 제일 좌측 집에는 반드시 설치한다. 3. mid 거리마다 거리가 일치하거나 가장 좌측 가까이 있는 집에 설치한다. 4. 카운트를 비교하여 left, right 를 조정한다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int c = sc.nextInt(); int a[] = new int[n]; for(int i=0; i

문제 설명이 장황하지만 기타 레슨과 완전히 똑같은 문제이다. 입력값의 범위와 출력 패턴도 똑같아서 Ctrl + C, Ctrl + V 를 해도 된다;; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int a[] = new int[n]; int left = 0; int right = 0; for(int i=0; i left ? a[i] : left; right += a[i]; } while(left

이분 탐색으로 문제에서 요구하는 블루레이 크기를 구하는 문제다. 1. 최소값은(left) 레슨의 수 중 가장 작은값으로 한다. 2. 임의로 정한 블루레이 크기((left + right)/2)에 레슨을 순차적으로 담는다. 2-1. 레슨의 길이가 블루레이의 크기를 초과하게 된다면 블루레이 크기를 증가시킨다. 3. 블루레이의 개수가 m 보다 작다면 최대값(right)를 줄인다. 3.-1. 블루레이의 개수가 m 보다 같거나 크다면 최소값을 줄인다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int a[]..