반응형 Problem Solving/BOJ228 백준 2529번 부등호 - C++ 풀이 1. 부등호 조건에 맞게 중복 없이 숫자를 하나씩 뽑는다. 2. k+1개를 다 뽑았으면 최대, 최소 정수를 업데이트한다. 1. 부등호 조건에 맞게 중복 없이 숫자를 하나씩 뽑는다. 백트래킹으로 풀 수 있다. 부등호 조건에 맞으면서 중복 사용이 없도록 숫자를 하나씩 뽑아나간다. 2. k+1개를 다 뽑았으면 최대, 최소 정수를 업데이트한다. 부등호가 k개이므로 총 k+1개의 숫자를 뽑아야 한다. 다 뽑았으면 완성된 정수를 구하여 최대, 최소 정수를 업데이트한다. 이때는 문자열을 활용하면 편하다. #include using namespace std; int k; char signs[10]; int pick[10]; bool is_used[10]; string max_ans = "0000000000", min_.. 2023. 8. 3. 백준 14719번 빗물 - C++ 풀이 1. 각 열마다 고이는 빗물의 양을 구해 합친다. 2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다. 3. 그 중 더 낮은 블록 높이까지 빗물이 고이게 된다. 1. 각 열마다 고이는 빗물의 양을 구해 합친다. 각 열마다 고이는 빗물의 양을 구한 뒤 합치는 방식으로 전체 고이는 빗물의 양을 구해준다. 이때 양 끝 열(제일 왼쪽과 오른쪽)에는 절대 빗물이 고일 수 없다. 2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다. 빗물이 고이기 위해서는 그릇의 형태가 되어야 한다. 즉, 양쪽이 i열보다 더 높은 블록으로 막혀있어야 한다. (양 끝 열에는 절대 빗물이 고일 수 없는 이유이다.) 또한 그.. 2023. 7. 24. 백준 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. 이전 1 2 3 4 5 6 ··· 46 다음 반응형
