유형: 그리디 문제: 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/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 풀이 문제를 이해하는게 조금 시간이 걸린다. 판자는 가로/세로 두 타입이 있고 바닥 장식을 만들 때 사용된다. ---- 의 경우에는 가로형 판자 한개만 있으면 된다. -|||의 경우에는 가로형 판자 1개, 세로형 판자 3개가 된다. search 함수에서는 처음 입력이 가로/세로 어느 쪽인지 판단하고 세로면 x의 인덱스를 1씩 추가하여 탐색, 가로면 y의 인덱스를 1씩 추가하여 탐색했..
유형: dp 문제: https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 풀이 길이가 30까지인 파스칼의 삼각형을 미리 계산해둔 후, 입력값의 크기만큼 해당 값을 더해주면 된다. 입력값에서 r, c는 인덱스 크기에 맞춰 -=1을 해줘야 한다. (인덱스는 0부터 시작하기에) 세로의 크기는 r-1이상 r+w미만, 가로의 크기는 c-1이상 c+width미만이다. width의 크기는 첫번째 for문에서 한번씩 +=1을 해주면 된다. #include "vector" #inclu..
유형: 그리디 문제: https://www.acmicpc.net/problem/11256 11256번: 사탕 당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다. 당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰 www.acmicpc.net 풀이 상자는 최대 가로*세로의 개수만큼 사탕을 담을 수 있다. 가로*세로 값을 벡터에 저장한 뒤, 내림차순으로 정렬한다. 그리고 벡터 원소를 하나씩 돌면서(가장 큰 값부터 보게 된다) 전체 사탕 개수 -= 원소값 으로 갱신한다. 이때 사탕 개수가 0 이하가 된다면 사탕을 전부 담게된다. #include "iostream" #include "vector" #include "algor..
