hyeonae

문제 햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다. 예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 ..

풀이 열린 괄호 '(' 가 닫힌 괄호 ')' 와 한 쌍이 되면 YES, 그렇지 않다면 NO를 출력하는 전형적인 스택 문제이다. 문자열의 괄호를 관리할 스택 자료구조를 먼저 만들었다. 이제 입력받은 문자열에 for 문을 돌려보자. 1. '('를 만나면 스택에 '('를 넣는다. 2. ')'를 만나면 '('와 한 쌍을 만들어주기 위해 스택에서 '('를 꺼낸다. 2-1. 스택이 비어있다면 ')'와 한 쌍을 이루는 '('가 없다는 뜻이기 때문에 "NO"를 출력한다. 3. for 문이 끝났는데 스택이 비어있지 않다면 '('가 남는다는 뜻이기 때문에 "NO"를 출력한다. 코드 #include #include using namespace std; int T; void init() { cin.tie(0); cout.ti..

예제 풀이 이 문제는 다이나믹 프로그래밍(DP) 기법을 통해 쉽게 풀 수 있다. 예제를 보면, 각 줄마다 i번째 집을 빨강으로 칠했을 때, 초록으로 칠했을 때, 파랑으로 칠했을 때 비용이 입력 값으로 들어온다. 먼저 입력값을 dp[1001][3] 배열에 저장한다. dp[0][0]은 0번째 집을 빨강으로 칠했을 때 비용, dp[0][1]은 0번째 집을 초록으로 칠했을 때 비용, dp[0][2]는 0번째 집을 파랑으로 칠했을 때 비용을 의미한다. 입력이 끝난 다음, 다이나믹 프로그래밍(DP) 기법을 통해 이웃하는 집과 색이 겹치지 않도록 칠했을 때의 최소 비용을 구한다. for문을 돌면서 i번째 집에서 3가지 색깔로 칠했을 때의 최소 비용을 각각 계산해 dp[i][0] ~ dp[i][2]에 다시 저장한다. ..

풀이 유명한 그리디 알고리즘 문제 중 하나다. 회의들의 시작 시간과 끝나는 시간이 주어지면, 회의실 하나로 할 수 있는 최대의 회의 개수를 출력해야 한다. 문제를 풀기 위해서는 회의들을 끝나는 시간이 빠른 순서대로 재정렬해야 한다. 끝나는 시간이 빠를 수록 다음 회의를 넣을 수 있는 시간대가 커지기 때문이다. 반복문 안에서 차례대로 이전 회의와 시간대가 겹치지 않는지 확인하고, 겹치지 않는다면 회의 개수를 하나씩 늘리도록 한다. 코드 #include #include #define MAX 100020 using namespace std; typedef struct { long long start; long long end; } meeting; bool compare(meeting& a, meeting& b..

풀이 간단한 그리디 문제이다. 가장 짧은 시간이 걸리는 사람부터 차례로 정렬한 다음, 각 사람들이 인출하는데 걸리는 시간을 더해주면 최소값을 구할 수 있다. 코드 #include #include #define MAX 1001 using namespace std; int N, answer = 0; int P[MAX]; void init() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int main() { cin >> N; for (int i = 0; i > P[i]; } sort(P, P + N); for (int i = 0; i < N; i++) { answer += (P[i] * (N - i)); } c..

풀이 답답해서 결국 풀이를 찾아봤다. 그냥 가장 작은 숫자부터 지워주면 되는 줄 알았는데, 덱 또는 스택과 그리디 알고리즘을 함께 사용해야 하는 문제였다. 첫번째 숫자부터 차례대로 덱에 넣어주면서 지금 숫자가 덱에 있는 숫자보다 더 큰 지 검사한다. 만약 덱에 있는 숫자보다 더 크다면 덱에 저장된 작은 숫자들을 모두 pop해 지워주고, 지운 개수만큼 K를 하나씩 감소한다. 만약 지운 개수가 적어 K가 남아있다면 (N-K) 개 만큼 덱의 앞에서부터 출력해주면 된다. 코드 #include #include using namespace std; int N, K; string input; deque d; void init() { cin.tie(0); cout.tie(0); ios_base::sync_with_st..