유형: 그리디 문제: https://www.acmicpc.net/problem/14469 14469번: 소가 길을 건너간 이유 3 첫 번째 소는 2초에 도착하고 3초에 농장을 입장한다. 그 다음에는 세 번째 소가 5초에 도착하여 12초에 농장을 입장한다. 마지막으로 두 번째 소가 8초에 오는데, 세 번째 소가 검문을 받고 있으 www.acmicpc.net 풀이 입력을 받아와 pair 형식으로 벡터에 저장하고, 시작 시간이 낮은 순으로 정렬한다. 만약 시작 시간이 같다면 소요 시간이 낮은 순으로 정렬한다. 이런 조건대로 정렬한 뒤, 벡터 원소를 순회하면서 조건에 따라 시간을 더하면 된다. 현재 시간을 cnt라고 할 때, cnt가 원소 시작 시간보다 작다면, cnt를 시작 시간으로 갱신한다. 이는 다음 소가..
유형: 그리디 문제: https://www.acmicpc.net/problem/2810 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 풀이 한 좌석에 양 옆에 컵홀더가 있다. 한 좌석의 단위는 S, LL이다. 모든 좌석의 왼쪽에 컵홀더를 배치한다. 그리고 마지막 좌석은 오른쪽에 컵홀더를 배치한다. 이게 전체 컵홀더의 개수다. *S *S *LL *S *S* 이 경우를 참고 바람. 전체 사람수는 문자의 총 개수와 같고 (입력으로도 주어진다) 컵홀더의 개수는 S의 개수 + (L의 개수 / 2) + 1 이다. 1은 맨 마지막 좌석의 오른쪽 컵홀더를 의미한다. 컵홀더가 사람수보다 작거나 같으면 컵홀더 수가 정답이다..
유형: 그리디 문제: https://www.acmicpc.net/problem/11256 11256번: 사탕 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰 www.acmicpc.net 풀이 상자는 최대 가로*세로의 개수만큼 사탕을 담을 수 있다. 가로*세로 값을 벡터에 저장한 뒤, 내림차순으로 정렬한다. 그리고 벡터 원소를 하나씩 돌면서(가장 큰 값부터 보게 된다) 전체 사탕 개수 -= 원소값 으로 갱신한다. 이때 사탕 개수가 0 이하가 된다면 사탕을 전부 담게된다. #include "iostream" #include "vector" #include "algor..
유형: 그리디 문제: https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 풀이 첫 번째 나무는 1일차에 심는다. 그리고 0부터 시작한다. [2, 3, 4, 3]의 경우, 2일 걸리는 나무를 첫 번째로 심는다 치면, 1일차에 0부터 시작, 3일차에 2가 된다. 그러니 각 나무가 다 자라는데 걸리는 시간은, 각 배열의 원소값 + (인덱스 + 1) 이다. 1일차부터 시작한다는 것은, 배열 순서를 세는 기준을 1로 잡는것과 동일..
유형: 그리디 문제: https://www.acmicpc.net/problem/6550 6550번: 부분 문자열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다. www.acmicpc.net 입출력 방식 입력받는 개수가 몇개인지 모르는 경우이다. 이런 경우를 입력받는 방법은 여러 가지가 있는 것 같다. 이 글에 정리가 잘 되어있다! https://scarlettb.tistory.com/69 가장 직관적인 방법은 while문 조건에 cin 또는 scanf를 넣는 것이다. 다만 scanf를 넣을 땐 scanf(...) != EOF 형식으로 써야하는 것 같다. do whil..
