본문 바로가기
반응형

Problem Solving242

프로그래머스 이모티콘 할인행사 - C++ 풀이 1. 4가지의 할인율을 가질 수 있으므로 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 2. 비트마스크를 사용하여 이모티콘들의 할인율을 설정하는 모든 방법을 탐색한다. 3. 서비스 가입자 수가 가장 많은 방법, 서비스 가입자 수가 같다면 판매 금액이 가장 높은 방법을 선택한다. 1. 4가지의 할인율을 가질 수 있으므로 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 각 이모티콘별로 총 가지, 10%, 20%, 30%, 40% 중 하나의 할인율을 갖는다. 따라서 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 이모티콘의 개수 n은 최대 7로 매우 작기 때문에 모든 경우를 다 탐색하는 브루트포스를 사용하더라도 제한시간 내에 해결이 가능하다. 2. 비트마스크를 사용.. 2023. 7. 22.
백준 4097번 수익 - C++ 풀이 1. dp[i] = i일로 끝나는 구간 중 최고수익 구간의 수익 2. dp[i] = i-1일로 끝나는 최고수익 구간에 i일을 추가하거나 i일로 구간을 새로 시작하는 경우 중 최댓값 1. dp[i] = i일로 끝나는 구간 중 최고수익 구간의 수익 dp[i]를 위와 같이 정의하자. 예를 들어, dp[3]은 1-3일인 구간, 2-3일인 구간, 3-3일인 구간 중 최고 수익인 구간의 수익이다. 2. dp[i] = i-1일로 끝나는 최고수익 구간에 i일을 추가하거나 i일로 구간을 새로 시작하는 경우 중 최댓값 구간은 연속된 일자로 이루어져 있다는 성질을 이용한다. i일로 끝나는 구간은 1. i-1로 끝나는 구간에 i일을 추가하거나, 2. i일로 시작하면서 끝나는 구간(i일로만 이루어진) 둘 중 하나이다. 이 두 .. 2023. 7. 17.
백준 20303번 할로윈의 양아치 - C++ 풀이 1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다. 2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치) 3. 배낭의 최대 용량이 K-1인 냅색 문제로 바꾸어 푼다. 1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다. 친구끼리는 모두 한꺼번에 사탕을 빼앗기게 되므로 개인이 아니라 친구집합 단위로만 의미가 있다. 각 아이를 노드, 친구관계를 간선으로 생각하면 친구집합은 그래프의 각 연결요소가 된다. 이제 DFS/BFS 혹은 유니온파인드를 사용하여 모든 연결요소를 구해주자. 이때 각 연결요소에 속하는 노드(아이)의 개수와 각 노드에 걸린 사탕의 총합도 구한다. 2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치) 이.. 2023. 7. 14.
백준 27172번 수 나누기 게임 - C++ 풀이 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 3. 각 xi에 대해 xi의 모든 약수들과 결투한다. 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 두 수가 서로 약수와 배수 관계인 경우에만 점수에 변화가 생긴다. 따라서 주어진 수들의 약수&배수 관계에만 집중하자. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 어떤 수 x의 모든 약수는 1부터 sqrt(x)까지로 모두 나누어떨어지는지 확인하는 방식으로 구할 수 있다. 만약 x가 i로 나누어 떨어진다면, i와 x/i는 x의 약수이다. 이때 i = x/i인 경우는 주의하여 처리하여야 한다. 2. 각 xi에 대해 xi의 모든 약수들과.. 2023. 7. 9.
백준 21736번 헌내기는 친구가 필요해 - C++ 풀이 1. 현재 상황을 그래프로 나타낸다. 2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다. 3. 방문한 노드가 'P'인 경우 카운트한다. 1. 현재 상황을 그래프로 나타낸다. 주어진 상황은 그래프로 변환할 수 있다. 벽이 아닌 칸을 노드로 생각하고, 상하좌우로 인접한 칸들을 간선으로 잇는다. 2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다. 도연이와 A라는 노드가 연결되어 있다면, 도연이는 A를 만날 수 있다는 뜻이다. 도연이와 연결된 노드를 모두 찾기 위해 'I' 노드에서 시작하는 BFS/DFS로 그래프를 탐색하자. 3. 방문한 노드가 'P'인 경우 카운트한다. 각 노드를 방문하면서 해당 노드가 'P', 즉 사람인 경우 도연이가 해당 사람을 만날 수 있음을 의미하므로 카운트 + 1.. 2023. 7. 9.
반응형

티스토리툴바