Problem Solving (25) 썸네일형 리스트형 2624 동전 바꿔주기 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 전형적인 DP 문제이다. 이차원 배열 dp를 만들고 dp[i][j]에는 i번째 동전까지 사용했을 때, j원을 만들 수 있는 가능한 경우의 수를 저장하는 방식으로 해결했다. C++ 더보기 #include #include using namespace std; int cnt, k; int main(void) { cin.tie(nullptr); ios_base::sync_with_stdio(false); int t; cin >> t >> k; vecto.. 1707 Maximum XOR With an Element From Array 이번 문제는 Trie 구조를 이용해서 푸는 문제인데, Trie로 푸는 알고리즘 문제는 처음이었고, 그래서 풀 때, 시간이 좀 걸렸었다. 문제는 nums 배열에서 Queries 배열의 각 query의 두 번째 원소보다 같거나 작은 원소들과 첫 번째 원소와 XOR 연산을 했을 때의 최댓값을 찾는 문제이다. 어떠한 수 n과 임의의 수에 대해 XOR연산을 할 때, 만약 임의의 수가 5(101)와 4(100)라면, 공통되는 부분인 10의 계산 결과를 저장할 수만 있다면, 2번 계산하지 않아도 될 것이다. 이 문제에서는 XOR연산의 이러한 점을 이용하여 비트 레벨에서 Trie구조를 만들어 문제를 풀 것이다. 일단 우리가 짤 Trie는 root가 상위 비트, child가 하위 비트인 Trie이다. 그래서 querie.. 1706 Where Will the Ball Fall 이 문제도 조금 색다르긴 한데 어쨌든 전형적인 DFS 문제이다. C++ 더보기 class Solution { public: vector findBall(vector& grid) { vector res(grid[0].size()); for(size_t i = 0; i < res.size(); ++i){ size_t j = i, s = 0; while(res[i] == 0 && s < grid.size()){ if(grid[s][j] == 1){ if (j == res.size() - 1 || grid[s][j + 1] == -1) res[i] = -1; else{ ++j; ++s; } } else if (grid[s][j] == -1){ if (j == 0 || grid[s][j - 1] == 1) res.. 1705 Maximum Number of Eaten Apples 이 문제는 먼저 썩는 사과 먼저 먹어야 하는 전형적인 우선순위 큐 문제이다. C++ 더보기 class Solution { public: int eatenApples(vector& apples, vector& days) { using mypair = pair; priority_queue pq; int cnt{}; size_t i; for(i = 0; i < apples.size() || !pq.empty(); ++i){ while(!pq.empty() && pq.top().first 0) pq.push(top); } else{ int offset = min(top.first - int(i), top.second); cnt += offset; i += offset - 1; } } } return cnt; }.. 1704 Determine if String Halves Are Alike 이 문제는 주어진 문자열을 이등분한 후, 각 문자열에 포함된 모음의 수가 같으면 true를 반환하는 문제다 별다른 거 할 필요 없이 문제 그대로 구현하면 된다. C++ 더보기 class Solution { public: bool halvesAreAlike(string s) { map score; score['a'] = 1; score['e'] = 1; score['i'] = 1; score['o'] = 1; score['u'] = 1; score['A'] = 1; score['E'] = 1; score['I'] = 1; score['O'] = 1; score['U'] = 1; int a = 0, b = 0; for(size_t i = 0; i < s.length() / 2; ++i) a += score[.. 1713 Minimum Operations to Make a Subsequence 이 문제는 주어진 배열 arr이 target을 subsequence로 만드는 배열로 되려면 몇 번의 insert를 수행해야 하는지를 묻는 문제이다. 최장 공통부분 배열로 생각하기 쉽지만 아쉽게도 그렇게 풀면 시간 초과가 걸린다. 그래서 이 문제는 주어진 배열 arr이 문자열이 아니라 숫자로 구성되어 있으며, target의 원소가 모두 1번만 나타난 것에 유의해서 최장 증가 부분 수열로 풀어야 한다. =============================== 여담으로 포스팅한 1710부터 1713까지는 위클리 콘테스트 222의 문제이다. 이 콘테스트 1등이 23분만에 다 풀었는데 이쯤 되면 ICPC 올솔 할 수 있으려나 ㅋㅋㅋㅋㅋㅋ C++ 더보기 class Solution { public: int minOp.. 1712 Ways to Split Array Into Three Subarrays 숫자로 구성된 배열을 각각 mid의 합은 left의 합보다 같거나 크게, right의 합은 mid의 합보다 같거나 크게 3조각으로 나눌 수 있는 경우의 수를 구하는 문제이다. 이 문제는 정렬된 배열에서 특정한 값을 찾는 전형적인 이진 탐색 문제로, 누적합이 저장된 배열을 만들고, 그 배열에서 mid가 될 수 있는 최소 인덱스와 최대 인덱스를 찾으면 된다. 그리고 이진 탐색 말고도, 투 포인터로 풀린다. 나도 처음에 이진 탐색 말고도, 투 포인터로 하려고 했는데 예외 처리에서 애먹어서 그냥 이진 탐색으로 풀었다. 코드는 Discuss 뒤지면 나온다. C++ 더보기 class Solution { public: int waysToSplit(vector& nums) { vector sum(nums.size()).. 1711 Count Good Meals 입력으로 주어진 음식들 중에서 두 개를 선택했을 때, 맛있는 정도의 합이 2의 지수가 되는 경우의 수를 찾는 문제이다. 문제를 봤을 때, 바로 조합을 이용하는 방법이 생각났지만, 시간 복잡도 상 당연히 조합은 안 되었다. 그래서 일단 맛있는 정도를 Key, 등장 횟수를 value로 하는 해쉬맵을 만들고, 해당 해쉬맵을 순회하면서 모든 경우의 수를 찾는 시간복잡도 O(N)의 방법으로 해결했다. 여담으로 리트코드 채점 서버가 좀 이상한 거 같다. 같은 코드를 제출해도 수행시간이 2배까지도 차이가 났다... 음... 백준처럼 채점 서버에 제출이 몰리면 순차적으로 수행하는 게 아니라 그냥 동시에 돌리는 건가 C++ 더보기 class Solution { public: int countPairs(vector& de.. 이전 1 2 3 4 다음
