https://www.acmicpc.net/problem/20300 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 배열에서 두 수 $t_a$ 와 $t_b$ 를 골라 더해서 $K$를 만들고, 이 $K$들의 최댓값이 최소가 되도록 하는 문제. 더하는 두 수를 선택하는데 있어서, 정렬된 배열의 양 끝, $MAX_t$ 와 $MIN_t$ 를 더하는게 $K$를 작게 만들수 있는 방법이다. 가장 큰 수와 가장 작은수를 매칭시켜줘야 가장 큰수에 최소한의 수를 더할 수 있기 때문이다. 이 방법으로 배열의 크기가 짝수라면 깔끔하게 해결되지만, 배..

https://www.acmicpc.net/problem/16238 16238번: 독수리 첫째 날 1번 칸의 왼쪽에서 날기 시작해 2번 칸의 양을 먹는다. 독수리가 먹은 양의 수는 10마리이다. 2번 칸에 있는 양을 먹었기 때문에, 1번, 2번 칸의 양의 수는 0이 된다. 첫째 날의 밤에 양의 수 www.acmicpc.net 왼쪽 / 오른쪽에서 접근한다는 함정에 안 속아넘어가도록 조심해야하는 문제. 얼핏보면 순서에 굉장한 제약을 받을 거 같지만, 실제로 원하는 값들을 꺼내고자 할때 꺼내고자 하는 값들이 미리 결정된다면 그 값을 꺼내기 위한 최적의 방법은 유일해진다. 값 두개를 순서대로 꺼낼 때 왼쪽에서 접근한다면 더 왼쪽에 있는 값을 먼저 꺼내야 함은 자명하고, 오른쪽에서 접근한다면 더 오른쪽에 있는 값..

추천받아서 풀어본 그리디 문제. https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 처음에는 lis인가 생각했었는데 일단 이건 아니었다. 만약 swap 연산 후에 break 했다면 lis였을지도? 어떠한 숫자가 뒤로 가는 연산은 j 루프 한번으로 충분하기때문에 교환한 원소의 갯수를 기준으로 생각하면 정답에 도달하기가 힘들다. 어떠한 숫자 K에 대해서 swap을 진행한다고 할때, 지문에 나온 코드를 통해서 정렬하면 K는 j에 ..

입시를 대충 끝내고 PS재활을 시작하면서 접한 첫 문제. 거의 1년동안 문제를 안풀엇기때문에 바로 답이 안떠올라서 태그부터 까보았다. 태그는 그리디 / 정렬 정렬시켜놓고 숫자를 출력시킨 다음에 생각을 시작했는데 마지막 값으로 들어온 30이 이질적이게 큰 것을 보면서 다른 모든 숫자의 합으로 30이 만들어질수 없다는 생각을 했다. 다른 모든 숫자의 합 을 부분합으로 구해준 다음에 부분합으로 앞선 숫자들을 전부 사용해도 만들수 없는 수가 입력으로 있는 경우 부분합+1 이 답이 된다. 입력에 1이 없는 경우 숫자 1부터 만들수 없어 1을 출력해야하니 이부분에 대해서 처리가 필요할듯. AC받았다. 더보기 #include using namespace std; int arr[1234] = {0}; int prefi..

처음 보고 뇌절할뻔;; https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 처음에 든 생각은 일단 구간을 나누는 순서는 중요하지 않다 정도? 그냥 구간을 결과적으로 K-1개만큼 나누면 어찌저찌 잘 K개 나눠진 구간이 나옴. 이걸 나이브하게 완탐을 돌리면 nCr(3e5, K-1) 번 연산해야할거고 이건 너무나도 큰 숫자니까 이걸 줄여봐야함. 그리고나서 테스트케이스를 봤더니 1 3 5 6 10 에서 10만 따로 떨어져있는데, 이거랑 나눠진 (1,..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 지문부터 풀이과정까지 찔리는 문제... 과제를 가장 효율적으로 해결하려면 과제를 마지막날에 몰아서 하는게 가장 좋다. 몸으로경함하고있다. 그런데, 같은 날짜에 진행하려고 "다투는" 여러 과제의 경우에는, 가장 많은 점수를 받는 과제를 해결하는것이 당연히 효율이 좋다. 그래서 점수순으로 정렬해주고 해당 점수를 받을 과제를 처리할 날짜를 최대한 미뤄주면 정답이 된다. 더보기 #include using namespace std; vector v;..