백준 1931번 문제 바로가기 문제를 잘못 이해하는 것에서부터 풀어내는 데에 시간이 꽤나 많이 걸렸던 문제. 처음에는 여러 개의 회의실로 착각해서 아예 풀이 방향이 달랐고, 다음에는 “모든 경우의 수를 고려해야하나?” 고려하다보니 문제를 푸는 것이 어려웠다. 이 문제를 해결하는 방법의 주요 포인트를 시작시간이 아닌 종료 시간을 기준으로 정렬하자는 것이었다. 종료 시간을 기준으로 정렬하게 되면 같은 시간대에 최대한 많은 횟수의 회의를 열 수 있기 때문이다. 지금까지 풀어온 greedy 문제와는 결이 조금 달라서 당황을 많이했는데, 경험치를 더 늘려나가자! ...
백준 13305번 문제 바로가기 문제에 대한 첫 인상 보통 문제에 최소 비용 이라는 표현이 들어가면 greedy 알고리즘으로 풀어내는 경우가 많은 것 같다. 이 문제도 각 주유소에서 비용을 최소로 한 것이 전체 비용도 최소가 되도록 한다. 나의 풀이 솔직히 마지막 주유소의 price는 필요 없는 정보였다. 앞에서부터 차례대로 주유소를 지나오면서 이전까지의 기름의 최솟값보다 더 저렴하면 prev에 새로운 기름값을 저장하고, 비용을 구해나가면 된다. 시간-비용 그래프를 그려보면 점차 하강하는 계단식의 그래프 형태를 띈다. #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int main() { int N; // 주유소 갯수 vector<long long> distance; // 주유소 사이 거리 vector<long long> price; // 주유소별 리터당 가격 long long cost = 0; // 총 비용 long long prev = 1000000000; // 전 주유소 비용 long long temp; cin >> N; for (int i=0; i<N-1; i++){ cin >> temp; distance.push_back(temp); } for (int i=0; i<N; i++){ cin >> temp; price.push_back(temp); } for (int i=0; i<N-1; i++){ prev = min(prev, price[i]); cost += prev*distance[i]; } cout << cost; return 0; }
백준 19941번 문제 바로가기 문제에 대한 첫인상 처음에는 deque을 이용해서 풀어보려고 했다. H의 인덱스를 모아놓고 P를 기준으로 K범위에 H 인덱스가 포함되어있으면 pop하고 count을 1 늘리는 방식으로 구현했다. 하지만 사람보다 뒤에 있는 햄버거를 먹지 못하는(?) 알 수 없는 버그가 생겨서 갈아엎고 처음부터 다시 코드를 작성했다. 그냥 greedy하게 이중 for문을 돌려가며 만족하는 (H,P) 쌍이 있을 경우 H을 다른 문자(e.g ‘Y’)로 바꾸고 count을 1 늘리는 방식을 택했다. #include <iostream> #include <string> using namespace std; int main() { int N, K, count=0; string hp; cin >> N >> K; cin >> hp; for (int i=0; i<N; i++){ if (hp[i] == 'P'){ for (int j=i-K; j<i+K+1; j++){ if (hp[j] == 'H'){ hp[j] = 'Y'; count += 1; break; } } } } cout << count; return 0; }
프로그래머스 덧칠하기 문제 바로가기 문제에 대한 첫인상 처음 이 문제를 접했을 때 많이 당황했다. 최적의 경우를 어떻게 구하라는 건지… 특히 n과 m에 따른 관계를 파악하는게 어려워서 횟수를 기준으로 bruteforce해봐야하는지도 고민해보았다. 그런데 여러 예시들을 스스로 만들어보면서 n 변수는 솔직히 필요 없는 정보라는 점을 알게 되었다. 문제를 쉽게 바꾸면 section을 m길이 천막으로 모두 가리기 위한 천막의 갯수 정도로 생각해볼 수 있다. 따라서 section의 각 요소에 대해서 m 길이로 페인트를 칠하고, 칠해진 마지막 index을 업데이트 해나가는 논리를 따르면 greedy 방식으로 문제를 해결할 수 있다. ...
백준 1026번 바로가기 첫 번째 풀이 KMO 같은 수학 경시대회를 풀어본 경험이 있다면, 직관적으로 이 문제를 보자마자 A배열을 오름차순, B배열을 내림차순해서 각 원소를 곱해주면 되겠다는 발상을 떠올릴 것이다. 다음과 같은 코드로 쉽게 문제를 해결할 수 있다. import sys n = int(sys.stdin.readline()) arr_1 = sorted(list(map(int, sys.stdin.readline().split())), reverse=True) arr_2 = sorted(list(map(int, sys.stdin.readline().split())), reverse=False) ans = 0 for i in range(n): ans += arr_1[i] * arr_2[i] print(ans) 두 번째 풀이 다만, 이 문제의 경우 단, B에 있는 수는 재배열하면 안 된다. 라는 제한조건이 걸려있기 때문에 바람직한 풀이는 아니다. 위처럼 A, B배열 모두 정렬해서 제출하더라도 정답처리는 되지만, 출제 의도에 맞게 다시 풀어보자. A배열을 정렬한 상태에서 B에서 최솟값을 하나씩 뽑아내는 방법이다. 결국엔 같은 방법같긴 하지만, 문제의 취지에 맞게 greedy로 풀었다. ...