전형적인 그리디 문제이다. 일단, 문제를 보면 최소 비용을 계산하는 문제이므로 직관적으로 큰 것은 나중에 더하고 싶은 느낌이 든다. 이 지점에서 그리디 문제인지 의심해볼 수 있다. Greedy property를 증명하는 것은 생각보다 간단한데 결과적으로 n개의 element를 1개의 element로 만들기 위해서는 n - 1 번의 파일 합치기를 해야한다. 이때, Current status에서 가장 작은 element를 선택하는 것이 partially optimized하면서 globally optimized를 만족하게 된다. 이때, 계속해서 최소값을 불러와주는 작업을 거쳐야하므로 우선순위 큐 자료구조를 사용하면 된다. #include #define fastio ios_base::sync_with_stdio..

잘 생각해보면 최대한 큰 숫자들은 나중에 자르는 것이 유리하다. 왜냐하면 남아있는 숫자가 크면 클수록 곱해지는 것이 더 커지기 때문이다. 따라서 이 지점에서 정렬을 하고 작은 숫자들부터 choice하는 아이디어를 확보하면 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int main(void){ fastio; int n; cin >> n; vector data_store; int current_length = 0; for(int i = 0; i > temp; data_store.push_back(temp); current..

나누는 숫자들이 300, 60, 10이다. 다만, 이 숫자들은 배수 관계이므로 무조건 더 큰 것을 쓸 수 있으면 쓰는 것이 유리하다. 예를 들어 60 * 5나 10 * 30을 하는 것보다 300 1개 쓰는 것이 무조건 유리하다. 즉, 더 큰 단위로 표현할 수 있으면 무조건 해당하는 것부터 쓰는 것이 유리하다. 이 부분에서 그리디 문제임을 파악하면 된다. 쉽다 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int main(void){ fastio; int n; cin >> n; if(n % 10 != 0){ cout

문제를 보고 생각보다는 쉽게 그리디 문제임을 파악할 수 있다. 문제 조건을 잘 보면, 최대한 많은 시민이 마스크를 구매할 수 있도록 유도해야한다. 즉 상식적으로 이 워딩을 보면 모든 시민들이 구매할 수 있게끔 최적(?)의 방법으로 구매하는 것이 가장 이득이라는 것을 간파할 수 있다. 즉, 이 지점에서 그리디 문제가 아닐까 의심을 해볼 수 있다. 직관적으로 잘 생각해보면 마스크를 제일 많이 팔 수 있는 경우는 해당 마스크 가격에만 구매할 수 있는 사람을 최우선적으로 구매권을 주면 된다는 것을 간파할 수 있다. 즉, 이 문제를 풀기 위해서는 각 상점을 기준으로 해당 가격 마스크를 시민들의 구매할 수 있는지 여부를 체크하고 그 중 가장 최적의 케이스 순서대로 구매를 진행해야 한다. 다만, 이 문제에서 입력값이..

상황 자체는 쉽게 잡았으나, 구현에서 살짝 애를 먹었다. (사실 2시간 잔 상태로 기본 틀을 잡아서 몇번 더 틀렸다 ㅋㅋ) 일단 이 문제를 풀기 위해서 상황 자체를 바꿔가면서 상황을 이해하려 해야한다. 그러면 크게 3가지 상황으로 이 문제를 바라볼 수 있다. 1. 세로가 홀수인 경우 이 경우는 생각보다 매우 쉽다. ㄹ모양으로 계속해서 왼쪽, 오른쪽으로 타고 내려가면 된다. 구현 자체는 zero base로 짯다고 가정했을 때, 세로가 짝수이면 Right, 홀수이면 Left를 출력해주면 된다. 2. 세로가 짝수이나, 가로가 홀수인 경우 이 경우는 1번 케이스의 변형으로 사각형을 90도 돌렸다고 생각해보면 1번 케이스로 치환할 수 있다. 모양은 위 아래를 반복하면서 전체적으로 오른쪽으로 진행해주면 된다. 구현..

문제를 이리저리 돌려가면서 상황을 파악해가면 다음과 같은 상황임을 이해할 수 있다. "우주 정거장의 x, y 좌표 사이에 다른 우주 정거장이 존재하면 이동할 수 있다." 그런데, 문제에서는 질문에서 주어진 우주 정거장 사이의 이동 가능 여부를 물어보고 있으므로 일종의 위의 명제의 참/거짓 여부의 연결 양상을 판단하라고 하는 것과 동치이다. 따라서 위 문제가 상호 배타적 집합임을 파악할 수 있다. 따라서 Union-Find로 문제를 풀어주면 된다. 이 문제의 경향성은 백준 17619번 개구리 점프와 매우 유사한 양상을 띄고 있다. (viyoung.tistory.com/132) 다만, 이 문제에서는 x, y좌표를 모두 고려해야 하기 때문에 x기준으로 union, y기준으로 union을 시켜주면 된다. 추가적..

i번째까지의 집을 칠하기 위한 비용을 구하기 위해서는 i - 1번째 집의 색칠 상태가 필요하다 즉, dp[i][0~3] = i번째 index까지 칠했을 때 필요한 비용 (단, i번쨰 index를 칠한 색이 0이면 R, 1이면 G, 2이면 B) 따라서 점화식을 세워보면 구하고자 하는 답을 간단하게 구할 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int dp[1001][3]; int main(void){ fastio; memset(dp, 0, sizeof(dp)); int n; cin >> n; cin >> dp[0][0] >> dp[0][1] >> dp[0][2..

상당히 재밌게 풀은 문제이다. 이 문제를 풀기위해서는 여러 도로들을 거치면서 사람이 지나갈 수 있는 정도를 이해해야한다. 예를 들어 1번에서 2번으로 가기 위한 간선은 매 단위시간마다 2명이 들어설 수 있고 지나가려면 단위 시간 3이 필요하고 2번에서 3번으로 가기 위한 간선은 매 단위시간마다 1명이 들어설 수 있고 지나가려면 단위 시간 5가 필요하다고 하자. 그러면 1번에서 3번으로 가기 위해서는 간선 (1,2)와 (2,3)을 거쳐가야하는데 이 과정에서 두번째 간선의 유입량이 1로써 제일 작으므로 사실상 단위 시간당 3번으로 빠져나오는 양은 1이다. 즉, 빠져나오는 양은 간선의 단위 시간 당 들어올 수 있는 사람의 수의 최솟값이다. 사람의 유입되고 그것을 산출하는 방식이므로 Network flow로 이..