본문 바로가기
반응형

Problem Solving242

백준 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.
프로그래머스 표현 가능한 이진트리 - C++ 풀이 1. 주어진 십진수를 이진수로 변환한다. 2. 변환한 이진수는 트리를 중위순회한 결과와 같다. 3. 중위순회 결과를 가지고 포화이진트리를 만들었을 때, 부모는 더미노드인데 자식은 실제노드인 경우 표현 불가능한 구조이다. 1. 주어진 십진수를 이진수로 변환한다. 먼저 십진수를 이진수로 변환한다. 2. 변환한 이진수는 트리를 중위순회한 결과와 같다. 노드를 왼쪽부터 순서대로 살펴보는 것은 중위순회하는 것과 같다. 따라서 변환한 이진수는 트리를 중위순회한 결과와 같고, 이진수의 길이는 트리의 노드 개수와 같다. 포화이진트리는 노드의 개수가 2^n-1개이므로 포화이진트리가 되도록 부족한 길이는 0으로 채워준다. (더미 노드를 추가하는 것은 문제가 되지 않음) 3. 중위순회 결과를 가지고 포화이진트리를 만들었을 .. 2023. 7. 22.
프로그래머스 미로 탈출 명령어 - C++ 풀이 1. dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 도달할 수 있는지 여부 2. dp(r, c, k): dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc)가 하나라도 있는가 3. 이동방향에 대한 우선순위는 d, l, r, u이다. 1. dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 도달할 수 있는지 여부 dp(r, c, k)를 위와 같이 정의하자. R = C = 50, K = 2500이므로 구해야 하는 상태값의 개수는 50*50*2500개. 제한 시간 내에 모두 구하기 충분하다. 기저 사례는 k=0인 경우로 이때 위치한 칸이 도착지점인지 판단하면 된다. 2. dp(r, c, k): dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc.. 2023. 7. 22.
프로그래머스 택배 배달과 수거하기 - C++ 풀이 1. 배달은 갈 때, 수거는 돌아올 때 한다. 2. 최대한 먼 집부터 해결하는 것이 최적이다. 3. 배달할 상자와 수거할 상자가 모두 없어질 때까지 반복한다. 1. 배달은 갈 때, 수거는 돌아올 때 한다. 이동 거리를 최소화해야 한다. 물류센터에서 출발할 때 트럭을 배달상자로 가득 채우고 출발한다. 가면서 각 집에 상자를 배달하여 트럭을 비우고, 다시 물류센터로 돌아오면서 수거상자들로 트럭을 채워오자. 2. 최대한 먼 집부터 해결하는 것이 최적이다. 또한 이동 거리를 최소화하기 위해서는 최대한 먼 집부터 방문하는 것이 최적이다. (A= 0 || pp >= 0) { int dist = 0; // 트럭을 배달상자로 채움 truck = cap; // 배달은 갈 때 while (truck > 0 && dp >=.. 2023. 7. 22.
반응형

티스토리툴바