재원블로그 재원블로그

이 문제는 그리디 문제이다. 나는 배수 판정법이라는 것을 모르는 상태로 이 문제를 풀었다. 일단 30의 배수가 되려면 10의 배수가 되어야 하므로 0의 개수가 0개이면 -1을 출력했다. 그 다음 여러 숫자들을 보며 규칙성을 찾았는데, 자릿수마다의 수를 모두 더한 수가 3으로 나누어떨어지면 3의 배수가 된다는 사실을 찾았다. 그래서 반신반의한 마음으로 제출했는데 맞았다. 30의 배수 중 가장 큰 수를 출력하라고 했기 때문에 입력 스트링을 내림차순으로 정렬하면 당연히 제일 큰수가 나올 것이므로 그렇게 풀었다. #include #include #include using namespace std; int main() { string input; cin >> input; bool flag = false; for ..

이 문제는 그리디를 이용해서 푸는 문제이다. 내가 생각한 방법은 현재 위치의 cost와 다음 위치들의 cost들을 비교하고, 만약 현재 cost보다 크거나 같으면 넘어가고, 작은 cost가 나올때까지 간다음, 현재 위치에서 그만큼의 연료를 충전하고 해당 위치로 이동하는 것이었다. 그러나 구현 실수로 정답이 나오지 않았는데, 이는 for문을 돌리다가 현재 cost보다 작은 cost가 나오면 바로 break를 해버려 해당 위치까지 이동하는 계산이 빠졌기 때문이다. 다시 구현하니 바로 정답이 나왔다. 한 가지 주의할 점은 만약 while (true) 로 하고 if (index == N - 1) break; 이런식으로 구현하면 무한 루프에 돌아가게 되는데, 이는 만약 for문이 break로 끝나지 않고 끝까지 ..

이 문제는 그리디를 이용해서 푸는 문제이다. 병렬로 사용했을 때 한 로프에 걸리는 중량은 w/k 이다. 최대 중량은 로프 중 가장 작은 로프에 걸리는 중량의 최대이다. 따라서 (로프 중 최소 중량) = w / k 이고, w = (로프 중 최소 중량) * k 가 된다. 따라서 로프들을 내림차순으로 정렬한 뒤, 최대를 갱신해가며 루프를 돌리면 정답이 나온다. #include #include #include using namespace std; int main() { int N; vector rope; cin >> N; for (int i = 0; i > maxWeight; rope.push_back(maxWeight); } sort(rope.begin..

이 문제는 그리디를 이용해서 푸는 문제이다. 일단 완전 탐색을 이용하는 것은 입력이 10만이므로 불가능하다. 따라서 그리디를 사용해야 하는데, 여기서 중요한 것은 끝나는 시간에 대해 오름차순으로 정렬하고, 끝나는 시간이 같을 때 시작 시간에 대해 오름차순 정렬해야 한다는 것이다. 결국 얼마나 많이 회의실을 배정할 수 있냐이므로, 끝나는 시간이 일찍 끝날 수록 많은 배정이 가능하기 때문이다. #include #include #include #include using namespace std; bool compare(pair &a, pair &b) { if (a.second == b.second) { return a.first < b.first; } return a.second < b.second; } in..

이 문제는 다익스트라 알고리즘을 사용하는 문제이다. 한 지점에서 한 지점의 최단 거리를 구하기 때문에 다익스트라를 사용하면 쉽게 풀 수 있다. 주의할 점은 C++에서 우선순위 큐의 디폴트로 최대 힙이므로 cost를 -를 붙여서 넣어줘야 하고, pair 를 우선순위 큐 내부에 사용할 경우 first부터 우선순위가 부여되므로 cost, next 순으로 넣어줘야 한다. #include #include #include #include using namespace std; #define INF 100000000 vector edges[50001]; int dist[50001]; int dijkstra(int start, int end) { priority_queue pq; dist[start] = 0; pq.pu..

이 문제는 프로그래머스 level 3 문제이다. 이 문제를 처음에 풀 때 입력이 25 * 25 = 625로 작아 백트래킹으로 풀릴 줄 알았다. 그러나 방향이 4가지이기 때문에 모든 칸이 빈칸인 경우 각 칸마다 4가지씩, 즉 어림잡아 4^625 정도로 절대 시간 안에 풀 수 없다. 그래서 bfs를 떠올리게 되었고, 그 중에서 다익스트라 알고리즘과 유사한 형태가 떠올라 그 방식으로 풀었다. 다익스트라 알고리즘의 핵심은 우선순위 큐 사용인데, 처음에 방향에 따른 cost를 생각하지 않고 정해진 방향으로 풀면 정답이 나오지 않는다. 방향에 따른 루프를 시작할 때, 무조건 현재의 방향을 우선으로 고려해야 정답이 나온다. 또한 이미 저장된 cost와 현재 값을 비교할 때 그 값이 같을 때에도 큐에 값이 들어가야 한..

이 문제는 프로그래머스 level 3 문제이다. 처음에는 완전 탐색을 이용해서 풀어보려고 했지만, 당연히 시간 초과가 났다. 징검다리의 횟수가 최대 2억번이기 때문이다. 그래서 그 다음으로는 스택을 사용하는 것처럼 i번째에서 이전 돌들과 비교해서 같거나 큰 징검다리가 나올때까지의 횟수를 세고, 이 값이 k보다 크면 그 높이를 정답으로 내는 방식으로 풀었다. 그러나 이 방식으로는 징검다리가 내림차순으로 되어있는 경우 제대로 된 값이 나올 수 없다. 구글링을 해서 풀이를 보니 이분 탐색으로 문제를 풀 수 있었다. 입력이 큰 것부터 이분 탐색을 생각했어야 했는데 아쉬웠다. 이분 탐색을 생각만 한다면 굉장히 쉽게 풀리는 문제였다. #include #include #include using namespace st..

이 문제는 백트래킹과 맵을 이용해서 풀었다. solution의 첫 for문은 각 banned_id에 부합하는 user_id를 찾아내는 것이고, solve 함수는 이를 기반으로 백트래킹을 돌려 해당 조합이 사용되었는지 확인한 후, 사용되지 않았으면 1을 리턴하는 것이다. 입력의 크기가 user_id, banned_id 모두 8 이하로 매우 작아 완전 탐색으로 가능한 문제였다. #include #include #include #include using namespace std; vector banned_list[8]; map listUsed; bool userUsed[8]; int solve(vector ban, int bannedSize, int bannedIndex) { if (ban.size() == ..