문제 링크 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 - 시간복잡도 O(NlogN) = 정렬 O(NlogN) 후 투 포인터 O(N) 수행 - Integer 범위 내이긴 하지만, 초기화시 일부 long 선언 처리 - M 만큼의 차이가 날 때까지 R을 먼저 탐색, A[R] - A[L] > M 조건 성립시 결과값 갱신 (최소값) 제출 코드 import java.util.*; import java.io.*; public ..

문제 링크 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 풀이 - 시간복잡도 O(N) - 1 (라이언 인형) 인 경우에만 카운팅 처리를 해주고, K개이상이 되는 연속된 인형의 집합의 길이는 L, R범위로 측정 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, K; static int[] A; static void input() throws Excep..

문제 링크 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 - 정렬 후 투 포인터 로직 수행 - 시간 복잡도 : O(NlogN) - 배열 순차적으로 순회하여 기준 값과 나머지 영역에서 투 포인터로 두 값을 정하고 다 더했을 때 0에 가까운 최대 값을 구하면 됨 참고 [BOJ 2470] 두용액 (Java, 투 포인터) [BOJ 1253] 좋다 (Java, 투 포인터) 제출 코드 - 입력 배열 A 의 데이터 타입을 lon..

문제 링크 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 풀이 - 알파벳(26자) 카운팅 배열을 활용하여 투포인터 문제 풀이 - 시간복잡도는 O(N) *알파벳 인덱스 구하기 int index = TEXT.char(i) - 'a'; 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, CNT; static String TEXT; static int[] ALPHABET ..

문제 링크 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 - 두 용액 문제 풀이 방법을 응용하여 풀이 - 시간 복잡도 O(NlogN) - 순차 조회하면서 해당 값을 다른 두 수의 합으로 만들 수 있는지 확인 (이때 탐색과정에서 자기자신의 경우 제외, targetIdx) 제출 코드 import java.util.*; import java.io.*; public class Main { static int N; static int[] A; static void input..

문제 링크 https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 - 투 포인트 기법과 카운팅 배열을 활용하여 1 ~ N 까지의 모든 경우의 수 합을 더하면 됨 - 시간복잡도 O(N) 이때 최대값의 경우 1 2 3 ... 100,000 1 2 3 ... 100,000 1 ~ 100,000까지의 합을 나타내기 때문에 100000(99999) / 2 = 대략 50억이기 때문에 long으로 풀이 해야 함 L = 1인 경우 100,000 L = 2인 경우 99..

문제 링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 - 투 포인터 문제 - 시간 복잡도 O(N) - 정답의 최대 길이는 100,000 , 구하려는 S의 최대는 10^9 이므로 Integer로 풀이 가능 제출 코드 import java.util.*; import java.io.*; public class Main { static int N, S; static int[] NUMBERS; static void input()..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 - 투 포인터로 문제 풀이 (이진탐색으로 풀이 가능하나 개념적으로 조금 어려움) - 두 용액을 더 했을 때 0에 가까운 두 수를 구하는 문제 - 양 끝에서 투 포인터를 시작해서 서로를 향해 이동 - sum 의 값이 양수인 경우 R을 감소, 음수인 경우 L을 증가 0 1 2 3 4 -99 -2 -1 4 98 -99, 98 = -1 이므로 L증가 -2..

문제 링크 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - long 타입 변수를 사용해야 하는 경우 있음 뒤집은 문제 용량(ml) 을 정했을 때, 친구(K)명에 막걸리를 골고루 분배 가능한가 ? 이때 용량(ml)는 최대인가? 부등호 헷갈리는 경우 주전자(N) 1개 이고 그 안에 21억ml가 담겨 있고, 친구(K) 100만명 있을 때 - 1000ml 로 나눌 경우 주전자에 1..

문제 링크 https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - 굴다리 길이 N (1 ≤ N ≤ 100,000) 일 때 0번 위치에 가로등 한 개 세울 경우 H는 100,000(최대)이 되야 모두 비추는게 가능하므로 Integer로 연산가능 뒤집은 문제 가로등 높이 H일 때 굴다리 길이 N을 모두 비추는게 가능한가? 가능한 경우 가로등 높이 H는 최소 높이인가? 예제 입력 1 5 ..

문제 링크 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 풀이 - 이진탐색(매개변수 탐색) 문제 - 시간복잡도 O(NlogN) - 은행 인출(mid) 하고 cnt = 1 한 초기 상태에서 일별 사용금액을 차감하면서 부족할 경우 추가 은행 인출(cnt += 1) - (100, 400), (300,100), (500), (101), (400) 형태가 최대값 만약 N일이 10만이고, 각 금액이 1만이면 최대 10^9이 되야 1번(M)번에 처리가 가능 =..

문제 링크 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 - 이진탐색 (매개변수 탐색) 으로 풀이하면 되는 문제 - 시간 복잡도는 O(NlogN) 범위 지정시 (L, R) L 의 경우 100,000개의 강의(N)를 100,000 개의 블루레이(M)에 담는다 할 때 (각 강의 길이 또한 최대 10,000분) 최소 10,000분이 되야함. 10,000분 이하는 담을 수가 없기 때문에, 최소 10,000분이 기준이 됨 L 은 고로 주어진 배열에서 가..

문제 링크https://www.acmicpc.net/problem/1300 1300번: K번째 수세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 Bwww.acmicpc.net2차원 배열을 1차원으로 이렇게 구할 수도 있다니 또 하나 배운다 :) 풀이 - N (최대 10만), K (10만 ~ 10억)- N * N 2차원 배열을, 1차원 배열로 변환 후 정렬했을 때 K번째 있는 임의 수를 구하는 문제 - N이 최대 10만이기 때문에 1차원 배열로 변환시 10^10 = 100억이 되어서 메모리 초과, 시간 초과 발생 가능 아래와 같은 연산..

문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이진탐색 (매개변수 탐색) 풀이하면 되는 문제 문제 지문 K개 랜선이 있을때 필요한 랜선 N개를 만들기 위한 최대 랜선 길이 H를 구하시오. 뒤집은 지문 (매개변수 탐색*) 임의 길이 H로 랜선을 K개를 자를때, 필요한 랜선 N개를 만들 수 있는가? 이때 최대 랜선 길이 H는 얼마인가? 시간 복잡도 O(NlogN) 최대값 랜선의 길이 최대값이 2^31 ..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 매개변수 (paramatrix search) 탐색 문제 (그리디 포함) 문제 지문 C 개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리(Dmax) 를 구하시오. 뒤집은 지문 두 공유기 사이의 거리 (D)를 라 할때, C개의 공유기를 설치 가능한가(yes/no)? 이때 설치 가능한 최대 거리(Dm..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 반복문을 통해 left = 1 ~ N 까지 조회할 때 - arr[left + 1 ... N] 사이에 값들 중 -arr[left] 이상이면서 가장 왼쪽에 있는 값을 찾아야 함 - N 이 최대 10만일때 O(N^2) = 10^10 시간초과 발생가능 - 이진탐색으로 풀이시 O(NlogN) 시간 복잡도 가짐 투 포인터로 풀 경우 좀 더 쉽게 풀이 가능 주..

문제 링크 https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 풀이 - 첫째줄에 점 N개가 주어지고, 다음 라인 부터 N개만큼 "위치 색깔" 형태로 입력이 주어짐 - 같은 색깔에 p와 q점에 대해 직선 화살표로 연결하려 할 때, 가장 가까운 거리의 점이여야 함 (만약 가까운 점이 두 개 이상이면 둘중 아무거나 선택) - 모든 점에 대해 같은 색깔을 가진 다른 점이 항상 존재 ( 2

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 - 길이가 N인 계단 수를 구하는 문제 (45656 처럼 인접한 모든 자리의 차이가 1인 수를 계단 수라 부름) - '이때 0으로 시작하는 수는 계단수가 아니다' 는 조건이 있음 점화식 - 2차원 DP배열에서 i, j 에 의미 부여 후 점화식 세워 문제 풀이하는 방법을 따라함 - 직접 했을 때는 식을 못 찾고, 설명을 찾아보고 다시 그렸을 때야 이해가 되었음 DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1] - 이때 DP[i][j] 에서 i는 자릿수(길이), j는 끝 숫자..