백준 20366 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 풀이 전 나의 생각 N개의 눈덩이가 주어졌을 때 2개의 눈덩이로 만든 눈사람 2개의 지름 차이가 최소가 되는 경우를 구해야 한다. 조건 - N (4 ≤ N ≤ 600) - Hi (1 ≤ Hi ≤ 109) - i (1 ≤ i ≤ N) 과정 문제를 푸는 방법은 두 가지가 있다. 첫 번째로 2중 for문을 이용하여 푸는 방법이 있다. 하지만 여기서 주의할 ..
알고리즘 및 자료구조/투 포인터
백준 2283 https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 풀이 전 나의 생각 수직선 상에 구간 N개와 두 정수 A, B (A < B) 가 주어질 때, A와 B에 포함 되어있는 구간의 합이 K가 되도록 하는 A와 B의 값을 구해야 한다. 조건 - 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000 - 양 끝점의 위치는 0 이상 1,000,000 이하의 정수 과정 (0, 0)부..
백준 2461 https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 풀이 전 나의 생각 KOI 중학교의 학급 N개와 각 학급의 학생 수 M이 주어질 때, 각 학급의 대표의 최댓값과 최소값의 차이가 최소가 되는 경우를 구해야 한다. 조건 - 1 ≤ N, M ≤ 1,000 - 능력치는 0이상 109이하 과정 N과 M이 1000개로 주어졌다고 가정 했을 때 단순 for문을 이용해서 모든 경우를 탐색할 시 1000 ^ 1000의 횟수가 나오..
백준 20922 https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 풀이 전 나의 생각 수열 N이 주어질 때, 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구해야 한다. 조건 - (1 > arr[i]; } while (end < N) { // 끝 포인터의 원소가 K개 미만 이라면 끝 포인터, 현재 연속된 부분 수열 길이 증가 if (visited[arr[end]] < K) { visited[arr[end]]++; end++; ..
백준 2531 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 전 나의 생각 회전 초밥의 벨트 상태가 주어졌을 때 쿠폰 초밥과 연속해서 먹을 수 있는 수를 고 려하며 최대 연속해서 먹을 수 있는 초밥의 가짓수를 구해야 한다. 조건 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한..
백준 22862 https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 풀이 전 나의 생각 길이가 N인 수열이 주어질 때, K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해야 한다. 조건 - 1 K; for (int i = 0; i > val; vec.push_back(val); } //시작 포인터, 끝 포인터, 홀수, 짝수, 최종값 int start = 0, end = 0..
백준 13144 https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 전 나의 생각 길이가 N인 수열이 주어질 때, 1개 이상의 연속된 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구해야 한다. 조건 - (1 ≤ N ≤ 100,000) - 수열에 나타나는 수는 모두 1 이상 100,000 이하 과정 수열 N이 10만의 범위로 주어지기 때문에 단순히 2중 for문을 이용한 풀이를 진행한다면 10만 * 10만의 계산 횟수로 시간 제한을 ..
백준 1806 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 전 나의 생각 N 길이의 수열이 주어질 때 연속된 수들의 부분합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구해내야 한다. 조건 - N (10 ≤ N < 100,000) - S (0 < S ≤ 100,000,000) - 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수 과정 목표 값 S는 1억 이하의 수기 때문에 데이터 타입을 int로..
