나그네

29767번: 점수를 최대로 문제 https://www.acmicpc.net/problem/29767 29767번: 점수를 최대로 단대소프트고에는 교실 $N$개가 있다. 교실은 $1$번부터 $N$번까지 $1, 2, \ldots, N$ 순서로 연달아 있다. 학교 밖에는 $K$명의 학생들이 있다. $K$명의 학생은 학교에 들어가기 전 학생마다 목적지 교실 www.acmicpc.net 풀이 목적지 i번 교실에 도착하면 1~i번 방의 점수를 얻습니다. 즉, 누적합 배열로 i번 교실을 목표로 했을 시 얻는 점수를 저장합니다. K명의 학생들은 서로 다른 목적지를 가지므로 누적합 배열을 내림차순 정렬하고 앞에서부터 K개 원소의 합을 출력하면 됩니다. 코드 #include using namespace std; #def..

29158번: 큰 수 만들기 게임 문제 https://www.acmicpc.net/problem/29158 29158번: 큰 수 만들기 게임 성현이와 지훈이는 큰 수 만들기 게임을 하고 있다. 성현이는 양의 정수 $N$이 적힌 카드 $1$장이 들어 있는 주머니를 들고 있다. 지훈이는 성현이의 카드를 몰래 본 다음 성현이의 카드에 적힌 $N$ www.acmicpc.net 풀이 큰 수를 만드는 테크닉은 16496 - 큰 수 만들기 문제와 동일하다. 각각의 수를 문자열로 a = "1", b = "2"인 경우 ab = "12" ba = "21"로 더 큰 수를 만들 수 있는 것은 ba다. 이 정렬 조건으로 수를 정렬한 다음 차례대로 나열하면 된다. 먼저 동작 1과 동작 2가 있는데, 동작 1은 2 이상의 K로 2..

29155번: 개발자 지망생 구름이의 취업 뽀개기 문제 https://www.acmicpc.net/problem/29155 29155번: 개발자 지망생 구름이의 취업 뽀개기 난이도 $1$에서 $1$분, $4$분, $4$분 순서로, 난이도 $2$에서 $5$분, 난이도 $3$에서 $20$분, 난이도 $4$에서 $40$분, 난이도 $5$에서 $100$분 순서대로 풀면 $1+3+4+0+4+60+5+60+20+60+40+60+100=417$분이 걸린다. www.acmicpc.net 풀이 각 난이도 별로 문제를 푸는 데 걸리는 시간을 저장하고 오름차순으로 정렬한다. 각 난이도별로 풀어야하는 문제의 수만큼 앞에서부터 고르면 된다. 이 문제에서는 문제를 푸는 데 필요한 시간을 최소화하고 휴식시간도 최소화해야한다. 휴식..

28703번: Double It 문제 https://www.acmicpc.net/problem/28703 28703번: Double It $31$에 $2$를 곱해서 $62$로, $41$에 $2$를 곱해서 $82$로, $51$ 에 $2$를 곱해서 $102$로, $3$에 $2$를 $5$번 곱해서 $96$으로 만들면, $A$의 최댓값 $102$와 최솟값 $62$의 차이가 $40$으로 최소가 됩니다. www.acmicpc.net 풀이 본 대회 때는 삽질만 종일 하다가 결국 못 푼 문제. 에디토리얼 참고해서 풀었다. 배열의 최솟값을 두배로 증가시켜 가며 최댓값과의 차를 최솟값으로 비교하며 업데이트한다. 이를 최솟값이 처음 배열의 최댓값보다 작을 때만 계속해서 반복한다. 최솟값 관리를 우선순위 큐로 하면 된다. 코..

23322번: 초콜릿 뺏어 먹기 문제 https://www.acmicpc.net/problem/23322 23322번: 초콜릿 뺏어 먹기 연두는 $N$개의 통에 초콜릿을 담아서, 초콜릿의 개수가 오름차순이 되도록 일렬로 배열해 놓는다. 즉, ($1$번째 통의 초콜릿의 개수) $\le$ ($2$번째 통의 초콜릿의 개수) $\le \dots \le$ ($N$번째 통의 www.acmicpc.net 풀이 이 문제에서 예제를 보면, 모든 통의 초콜릿 개수가 초콜릿 수가 가장 적은 통과 같도록 만든다. 입력받는 값 중 K는 사실상 필요없는 값이고, 입력받은 배열을 오름차순으로 정렬하면 0번 index의 값이 최솟값이 된다. 1번부터 N-1번 index까지 값을 순회하며 0번 index의 값(최솟값)보다 큰 경우에만..

18186번: 라면 사기 (Large) 문제 https://www.acmicpc.net/problem/18186 18186번: 라면 사기 (Large) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 풀이 [백준 / BOJ] 18185 라면 사기 (Small) 문제 / [백준 / BOJ] 18185 라면 사기 (Small) 풀이 위 문제를 먼저 풀고 난 후 풀면 비교적 쉽게 풀 수 있다. 위 문제와의 차이점은 1군데, 2군데, 3군데 구매했을 때 가격이 3, 5, 7이 아니라 b, b+c, b+2*c 라는 것이다. 즉, 위 문제는 ..

18185번: 라면 사기 (Small) 문제 https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 풀이 처음에는 앞에서부터 최대한 많이 3군데 연속해서 구매하고, 다시 앞에서부터 2군데, 그리고 낱개를 구매하도록 했으나 WA를 받았다. 2~3시간 정도 고민하다가 질문 게시판에서 반례 테스트 케이스를 얻어 2시간 정도 더 고민하고서야 풀었다. 0번 공장부터 차례대로 방문하며 아래 과정을 거친다. 1. i, i+1, i+2번째 공장에서..

28014번: 첨탑 밀어서 부수기 문제 https://www.acmicpc.net/problem/28014 28014번: 첨탑 밀어서 부수기 첫째 줄에 첨탑의 개수 $N$이 주어진다. $(1\leq N\leq 5\,000\,000)$ 둘째 줄에는 앞에서부터 차례대로 첨탑의 높이 $H_1, H_2, \cdots, H_n (1\leq H_i\leq 1\,000\,000)$ 이 주어진다. 입력으로 주어지는 모든 수는 정 www.acmicpc.net 풀이 밀려 넘어지는 첨탑의 높이가 바로 그다음 첨탑의 높이보다 클 때만 그다음 첨탑도 밀려 넘어진다는 것은 밀려 넘어지는 첨탑의 높이가 바로 그다음 첨탑의 높이보다 작거나 같을 때 다음 첨탑을 밀어야 한다. 즉, i번째 첨탑과 i+1번째 첨탑의 높이를 비교해 i+1..

27972번: 악보는 거들 뿐 문제 https://www.acmicpc.net/problem/27972 27972번: 악보는 거들 뿐 키위새는 피아노를 잘 치고 싶었지만 악보를 볼 줄 몰랐다. 그러다 동영상 사이트에서 수열만 보고 피아노를 연주하는 동영상을 찾아냈다! 하지만 동영상에서 보여주는 수에 맞는 음을 누르자 www.acmicpc.net 풀이 음의 높낮이가 변하면 수를 1씩 늘리고 줄이기만 하므로 가장 긴 연속된 증가/감소하는 부분 수열의 길이가 정답이 된다. 연속이 끊길 때 길이 초기화를 1로 해야 함에 주의하자. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int m, a = 1, b = 1..

27961번: 고양이는 많을수록 좋다 문제 https://www.acmicpc.net/problem/27961 27961번: 고양이는 많을수록 좋다 올바른 행동 순서가 될 수 있는 하나의 예시는 아래와 같으며, $4$번보다 더 작은 행동 횟수로 $6$마리의 고양이를 마도카의 집에 들이는 것은 불가능하다. 초기 상태($0$마리) $\rightarrow$ 생성 www.acmicpc.net 풀이 처음에 고양이는 0마리 있고, 1마리 생성하거나 현재 K마리의 고양이가 있으면 1~K마리의 고양이를 복제하는 것이 가능하다. 즉, 고양이가 1마리 이상 있을 때는 복제 연산만 사용하면 된다. 이때, 정확히 N마리의 고양이를 만들어야 하므로 2 * K ≥ N 이 되는 순간 연산이 종료된다. 따라서 2의 제곱승 꼴로 증가..