그리디

https://www.acmicpc.net/problem/1461문제 요약세준이는 현재 0에 위치책들도 0에 위치각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 둘 때 드는 최소 걸음수는?마지막에 0으로 돌아올 필요 X한 번에 최대 M권의 책을 들 수 있음시간 제한2초입력책의 개수 N과 한 번에 들 수 있는 책 개수 MN과 M은 50이하 자연수책의 원래 위치가 주어진다.0인 경우는 없으며, -10000~10000 범위 내 정수출력다 정리하는 데 필요한 최소 걸음 수 출력접근법테케1M = 2책 원래 위치(정렬) : -1 0 3 4 5 6 114번, 5번 책 두고 오기 ⇒ 5 + 5 = 10-1번 책 두고 오기 ⇒ 1 + 1 = 23번 책 두고 오기 ⇒ 3 + 3 = 66번, 11번 책 두기 ⇒ 11..

알고리즘 문제) BOJ 20960. Po 링크 : https://www.acmicpc.net/problem/20960문제 요약증강작업을 실시하여, 어떠한 수열을 만들었을 때, 최소 증강 횟수를 출력해라증강작업은 수열의 한 구간을 선택해 그 구간의 모든 요소를 특정 야ㅇ만큼 증가시킨 것을 의미한다.시간 제한1초입력수열의 길이를 나타내는 정수 n (1 ≤ n ≤ 100,000)n개의 0 이상 10^9 이하의 정수 ai증강 작업 이후의 수열을 의미출력가능한 최소 증강 작업 횟수인 m을 출력접근법특정 구간을 한번에 증가 시키면서 최소 횟수로 원하는 수열 형태를 만들어야함예시로 다음과 같이 주어졌을 때1 3 4 2 5 2 1 2위 그림처럼 연속된 구간별로(색깔로 구분) 증가시키면 최소 횟수만큼만 연산을 수행할 수..

알고리즘 문제) BOJ 2374. 같은 수로 만들기 링크 : https://www.acmicpc.net/problem/17178문제 요약n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가이때, A[i]의 좌우로 인접한 같은 수의 그룹도 한번에 1씩 증가이와 같이 Add라는 연산을 사용하여 A[1] = A[2] = A[3] = … = A[n]이 되도록 하려 한다소 회수로 Add연산을 사용하는 방법을 찾아라시간 제한1초입력첫째 줄에 정수 n다음 n개의 줄에는 차례로 A[1], A[2], …, A[n]든 입력은 1,000,000,000을 넘지 않는다출력첫째 줄에 최소의 Add연산 사용 회수를 출력값은 10^..

알고리즘 문제) BOJ 17299. 오등큰수 링크 : https://www.acmicpc.net/problem/17299문제 요약크기가 N인 수열 A1, …, AN이 존재수열의 각 원소 Ai에 대해 오등큰수 NGF(i)를 구하고자 한다오등큰수는Ai가 수열에서 등장한 횟수를 F(Ai)라 할 때Ai의 오등큰수는 Ai보다 오른쪽에 있으면서, 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중 가장 왼쪽에 있는 수를 의미없다면 -1시간 제한1초입력수열 크기 N1 ≤ N ≤ 100만수열의 원소 A1, … , An이 주어진다1 ≤ Ai ≤ 100만출력총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력접근법1 1 2 3 4 2 1등장 횟수 : 3 3 2 1 1 2 3 → 카운팅 배..

알고리즘 문제) BOJ 14725. 개미굴 링크 : https://www.acmicpc.net/problem/14725문제 요약로봇 개미로부터 얻은 개미굴 저장소를 바탕으로, 개미굴 구조를 출력해라예를들어, 아래와 같은 정보를 받았다면KIWI BANANAKIWI APPLEAPPLE APPLEAPPLE BANANA KIWI아래처럼 출력해라 APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA개미굴의 각 층은 "--" 로 구분하며, 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다시간 제한1초입력첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개두 번째 줄부터 N+1 번째 ..

알고리즘 문제) BOJ 31589. 포도주 시음 링크 : https://www.acmicpc.net/problem/31589문제 요약N종류의 포도주가 존재하며, 각각 맛을 지니고 있다이때, 첫 잔을 마실 때는 포도주 본연의 맛을 느끼지만그 이후부터 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 0의 맛을 느끼며맛없는 포도주를 마시다가 맛있는 포도주를 마시면 두 포도주의 맛의 차이만큼 느낀다이때 K종류의 포도주만 마신다 했을 때, 최대로 느낄 수 있는 맛을 구해라시간 제한1초입력포도주의 수 N, 마셔야할 포도주 수 K1 ≤ K ≤ N ≤ 30만N개의 포도주 맛 Ti가 주어진다1 ≤ Ti ≤ 10억출력맛의 합의 최댓값은?접근법순차적으로 먹게 될 경우 맛의 차이만큼 먹게된다.이때, 순차적으로 먹게 될 경우 ..

알고리즘 문제) BOJ 1727. 커플 만들기 링크 : https://www.acmicpc.net/problem/1727문제 요약여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명각 사람의 성격은 어떤 정수로 표시최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하자시간 제한2초입력첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)다음 줄에는 n명의 남자들의 성격그 다음 줄에는 m명의 여자들의 성격성격은 1,000,000이하의 자연수출력성격의 차이의 합의 최솟값을 출력접근법그리디 + dp로 풀어야 한다.최대한의 커플을 만들면서, 커플들의 성격차 합이 최소가 되게 해야함최대한의 커플을 만든다 == min(남학우 수, 여학우 수)만큼 만들어져야 함또한, 각 성별의..

알고리즘 문제) BOJ 3114. 사과와 바나나 링크 : https://www.acmicpc.net/problem/3114문제 요약R*C맵에 A나라와 B나라가 존재각 칸에는 A나무(사과) 개수, B나무(바나나) 개수가 주어짐(1,1)부터 시작해 (R,C)까지 불도저를 이동하면서 나무를 제거하고, 국경선을 만들려고함이때 국경선 아래는 A, 국경선 위는 B국가가 가지게 되는데,A나라는 사과를 좋아하고, B나라는 바나나를 좋아한다.따라서, 국경선 아래에 사과나무 개수 합과 국경선 위의 바나나 나무 개수 합이 최대가 되는 경우를 찾을 것시간 제한1초입력땅의 크기 R,C ( 2 ≤ R,C ≤ 1500)R개의 줄에 각 칸에 심어져 있는 나무 개수가 주어짐사과는 A, 바나나는 B이며 심어져 있는 나무 개수는 1~99..

알고리즘 문제) BOJ 22116. 창영이와 퇴근 링크 : https://www.acmicpc.net/problem/22116문제 요약창영이의 퇴근길은 N×N 크기의 격자로 표현각 칸에는 해당 지역의 높이가 적혀있음인접칸 높이차의 절대값 = 경사A1,1에서 출발하여 AN,N까지 이동할 계획상하좌우 인접 한 칸씩 이동 가능지날 수 있는 최대 경사의 최솟값 찾아보자시간 제한2초입력첫째줄 ; 격자 크기 N1 ≤ N ≤ 1,000둘째줄부터 N개 줄에 걸쳐 각 격자의 높이 정보가 주어짐첫 번째로 주어지는 값이 A1,1이고, 마지막으로 주어지는 값이 AN,N1 ≤ Ar,c ≤ 1,000,000,000출력A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력접근법dfs+dp로 풀면 3차원 배열이 필요하기때문에..

알고리즘 문제) BOJ 19590. 비드맨 링크 : https://www.acmicpc.net/problem/19590문제 요약서로 다른 두 종류의 구슬 두 개를 부딪히면 서로 깨져 없어짐이 사실을 이용해 현재 가지고 있는 구슬 개수를 최소화 하고자 함서로 다른 종류의 구슬 두 개를 부딪혀서 최대한 구슬을 없앤다고 할 때 남게 되는 구슬의 개수는 몇 개인지를 구하기시간 제한1초입력비드맨이 가지고 있는 구슬 종류 N1≤N≤10^5N개의 줄에 x1, x2, … , xN이 주어짐xi : 비드맨이 가지오 있는 i번째 종류의 구슬 개수1≤xi≤1억출력최대한 많이 구슬을 없앴을 때 남은 구슬 개수?접근법if 가장 큰 값을 제외한 나머지 친구들의 총 합 가장 큰 값 - 나머지 합if 나머지 합 == 가장 큰 값 → ..