Dev.baelanche

기존 점화식은 Y / X * 100 이지만 y에 비해 x가 무진장 크다면 0.0000xxxx.... 가 되어 100을 곱해도 0이 되게 된다. 따라서 Y * 100 / X 로 점화식을 짜주고 y * 100이 int의 범위를 벗어날 수 있으므로 long타입으로 해준다. X와 Y가 같지 않은 이상 절대로 확률이 100%가 될 수 없으므로 Y * 100 / X 가 99이면 -1을 출력한다. 그 외의 경우에는 이분탐색으로 기존의 승률보다 높으면서 판수가 가장 적을때를 찾아낸다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long x = sc.nextInt(); long y = sc..

일반적인 배열이나 부분합 배열로 풀면 시간초과가 난다. 나는 부분합 배열을 이분탐색하는 방식으로 풀었다. 이것말고도 풀이가 많을것 같은데 푼 사람이 얼마없어서 다른 방법은 못 찾았다. 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+1]; for(int i=0; i0) { int t = sc.nextInt(); int left = 1; int right = n; while(left t) right = mid-1; else left = mid+1; } System.o..

매 케이스마다 상근이의 카드 한개를 비교할 카드 배열의 길이를 반으로 쪼개며 이분탐색한다. 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]

n 배열을 오름차순으로 정렬하고 이분탐색으로 구현했다. 1. low, high는 각각 n배열의 최솟값, 최댓값으로 정했다. 2. mid 위치의 값과 현재 선택한 m 배열의 값을 비교하여 low, high 를 바꿔준다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.read..

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