본문 바로가기
반응형

알고리즘207

백준 10800번 컬러볼 - C++ 풀이 1. 공들을 크기 오름차순으로 정렬한다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) 1. 공들을 크기 오름차순으로 정렬한다. 먼저 공들을 크기 기준으로 오름차순 정렬해준다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) i번째 공보다 크기가 작고 색이 달라야 하므로, (i번째 공보다 작은 공들) - (i번째 공보다 작고 색이 같은 공들)을 구하면 된다. 포인터를 하나 두고, 포인터가 가리키는 공의 크기가 현재 공의 크기와 같아지기 전까지 포인터를 오른쪽으로 이동시키면서 1. 전체 크기 합과 2. 색깔별 크기 합.. 2022. 10. 5.
백준 16954번 움직이는 미로 탈출 - C++ 풀이 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 시간이 지남에 따라 미로가 바뀌고 있으므로, 상태 노드를 나타내기 위해 필요한 값은 행, 열, 그리고 시간 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. BFS를 사용하여 시작 노드 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 언제 도착했는지는 상관이 없기 때문에 r=0, c=7인 노드인지만 확인하면 된다. #include #include using namespace std; typedef.. 2022. 9. 30.
백준 13305번 주유소 - C++ 풀이 1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다. 1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다. 기름통의 크기가 무제한이므로, 그리디하게 각 도시에 도착하기 전에 가장 싼 주유소에서 기름을 넣고 오면 최적이다. 일반화하면, i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 주유소에서 넣고 오면 된다. 이때 i-1번 도시에서 i번 도시까지의 거리를 dist[i], 1~(i-1)번 도시 중 가장 싼 주유소의 가격을 min_price[i]라고 하면 비용은 dist[i] * min_price[i]이다. #include using namespace .. 2022. 9. 27.
백준 2616번 소형기관차 - C++ 풀이 1. sum[i] = arr[i...i+K-1]의 구간합 2. dp(idx, n): [idx번 객차~마지막 객차]가 있을 때 n개의 소형 기관차로 끌 수 있는 최대 손님의 수 3. dp(idx, n) = max(dp(idx+1, n), sum[idx] + dp(idx+K, n-1)) 1. sum[i] = arr[i...i+K-1]의 구간합 먼저 모든 길이 K인 구간의 구간합을 구해둔다. 누적합을 사용하여 O(N)에 구할 수 있다. sum[i] = sum[i-1] - arr[i-1] + arr[i+K-1] 2. dp(idx, n): [idx번 객차~마지막 객차]가 있을 때 n개의 소형 기관차로 끌 수 있는 최대 손님의 수 dp(idx, n)을 위와 같이 정의한다. 총 구해야 하는 상태 값은 50,000 *.. 2022. 9. 26.
백준 1726번 로봇 - C++ 풀이 1. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 세 가지 값이 필요하다. 2. 출발 상태 노드에서 도착 상태 노드까지 가는 최단 거리를 BFS를 사용하여 구한다. 1. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 세 가지 값이 필요하다. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 이 세 가지 값이 필요하다. 이것을 세 정보를 가지고 상태 노드를 구성할 수 있다. 2. 출발 상태 노드에서 도착 상태 노드까지 가는 최단 거리를 BFS를 사용하여 구한다. go k, turn left/right 연산을 통해 도달할 수 있는 상태 노드를 간선으로 이어 인접 노드로 만든다. 완성된 그래프에서 출발 상태에서 도착 상태로 가는 최단 거리를 구해준다. 모든 간선의 가중치가 1이므로 BFS를 사용.. 2022. 9. 23.
반응형

티스토리툴바