728x90 이분 탐색4 [JAVA]백준 1072번: 게임 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 1. 문제 설명 현재까지의 게임 횟수 X, 이긴 게임 Y이 주어진다. 지금부터 형택이는 게임을 하면 무조건 이긴다고 할 때 게임을 최소 몇 판을 해야 승률이 변하는지 구하는 문제. 2. 풀이 2가지로 풀이가 가능하다. 두 방법 모두 Z가 100, 99 일 때는 -1을 출력하고 98 이하일 때부터 계산을 수행한다. 99,100일 때 -1을 출력하는 이유는 99,100일 때는 아무리 게임을 더.. 2021. 7. 23. [JAVA]백준 1920번: 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 1. 문제 설명 N개의 정수 A [1], A [2].. A [N]가 주어진다. M개의 정수가 주어질 때, 이 수 들이 A[] 안에 존재하는지 알아낸다. 1 2021. 7. 20. [JAVA]백준 3020번: 개똥벌레 www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 1. 문제 설명 개똥벌레가 석순과 종유석으로 가득 찬 동굴에 들어갔다. 동굴의 길이는 N미터이고 높이는 H미터일 때 첫 번째 장애물은 항상 석순이고, 그다음부터는 종유석과 석순이 번갈아가면서 등장한다. 개똥벌레는 일직선으로 장애물을 파괴하면서 지나간다고 하였을 때, 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 문제이다. 2. 풀이 동굴의 길이 N (2 2021. 3. 30. [JAVA]백준 14003번: 가장 긴 증가하는 부분 수열 5 www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. 문제 설명 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하고 가장 긴 증가하는 부분 수열을 출력하는 문제이다. 2. 풀이 가장 긴 증가하는 부분 수열을 푸는 방법에는 여러 가지가 있는데 DP를 이용한 방법과 이분 탐색을 이용한 방법이 있다. DP를 이용하는 방법의 경우 O(N^2)의 시간 복잡도가 걸리고 이분 탐색의 경우 O(NlogN)의 시간 복잡도를 가진.. 2021. 2. 5. 이전 1 다음 728x90
