백준25 BOJ 1477 - 휴게소 세우기 https://www.acmicpc.net/problem/1477 접근휴게소 간 거리가 최소가 되는 거리를 찾는 문제이다.최소 거리를 찾는 문제이므로 매개변수 탐색을 통해 해결할 수 있다. 무엇을 기준으로 이분적으로 구분을 하면될까?휴게소 사이 (+ 시작지점과 끝지점 포함)에 새로운 휴게소를 건설한다는 가정하에 N의 거리를 두고 새로운 휴게소가 지어진다고 가정해보자.이렇게 되면 우리는 휴게소 사이에 둘 새로운 휴게소를 두는 지점을 이분적으로 탐색하면 된다. 예제 1번을 예를 들면휴게소 사이에서 어떤 거리 D을 기준으로 새로운 휴게소가 세워진다. 만약 휴게소 사이를 D으로 나누었을 때, 새롭게 세워진 휴게소가 M개가 넘는다면D를 늘려야 하므로 left = mid+1을 하면 된다. 반대로 새롭게 세워진 휴게.. 2024. 7. 12. BOJ 17404 - RGB 거리 2 https://www.acmicpc.net/problem/17404 접근기존 RGB 거리 문제에서 첫 번째 집과 마지막 집의 색을 고려하는 조건이 추가된 문제이다.DP를 이용하여 풀게되면 마지막 집을 칠할 때, 첫번째로 어떤 집을 선택했는지 알 수 없다.따라서, 첫 번째 집을 칠할 색을 저장하고 마지막 집의 색을 고려해야 한다. 첫 번째 집을 고르는 경우를 for문을 통해 선택하고, 기존 처럼 진행하면 된다.그러나 여기서 문제되는 부분이 있다. 첫 번째 집을 Red를 선택한다고 가정해보자.dp[1][1] = arr[1][1];for (int i = 2; i 위 코드에서 dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + cost[i][1];을 하는 순간 dp[1][1] 대신.. 2024. 7. 1. BOJ 11404 - 플로이드 https://www.acmicpc.net/problem/11404 접근모든 도시끼리 이동하는 비용 최솟값을 구하는 문제이다.시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.따라서, 모든 노드를 거쳐 시작 도시와 도착 도시를 이동하는 모든 노선을 확인해야 한다.이를 구현하기 적합한 알고리즘은 플로이드 와샬이다. 플로이드 와샬을 통해 중간 노드를 거쳐가는 모든 노선을 확인해보도록 하자.알고리즘은 매우 간단하다. 당연하지만, 시작 노드와 도착 노선 그리고 중간 노드를 모두 확인하기에 O(N^3)이 걸린다. 더보기#include #include #include #include using namespace std;#define MAX 9999999int n, m;int res[101][101];v.. 2024. 7. 1. BOJ 3109 - 빵집 3109번: 빵집 (acmicpc.net) 접근방법이번 문제는 그래프 탐색을 통해 오른쪽, 오른쪽 대각 위, 오른쪽 대각 아래 이렇게 총 3가지로 이동하며 마지막 열에 도달하는 문제이다.이 과정에서 발생하는 문제는 다음과 같다. 1. 어떻게 하야 가장 많은 파이프가 지나갈 수 있도록 배치할 수 있을까?2. 도착점까지 연결하는 파이프는 하나여야 한다. 먼저 1번부터 해결해보자.예제 1번을 보자 5 5.xx....x..........x....x. 여기서 0,0 에서 출발한 파이프 라인은 최대한 위쪽을 붙어서 이동해야 한다. 5 51xx.1.1x1...1.....x....x.이런게 1의 경로를 따라 이동해야 하므로, 움직이는 순서는 -1, 0 ,1 이어야 한다. (중요) 이제 2번째 문제인 "도착점까지 연결.. 2024. 4. 30. BOJ 1644 - 소수의 연속합 1644번: 소수의 연속합 (acmicpc.net) 접근 방법 투 포인터와 소수판별 알고리즘이 혼합된 문제이다. 소수 판별을 하기 위해 에라스토테네스의 체를 이용하여 소수를 배열에 저장한다. 해당 소수 배열을 투포인트를 돌면서 각 연속적인 수들의 합이 N이 될 때, 경우의 수를 + 1한다. 코드 #include #include #include using namespace std; #define MAX 4000001 #define ll long long bool chk[MAX+3]; vector arr; ll n, s; void func() { chk[1] = true; for (int i = 2; i < MAX; i++) { if(!chk[i]) arr.push_back(i); for (int j = i.. 2024. 4. 23. BOJ 1806 - 부분합 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 접근 방법 연속된 수들 중 합이 S 이상인 것들의 길이가 최소인 것을 구하는 문제이다. 전형적인 투포인터 유형의 문제로 쉽게 해결 할 수 있다. 문제에서 주의할 점이 S이상 이기 때문에 이 또한 고려해야 한다. 또한, 수의 범위가 꽤 크기 때문에 자료형 선정 시도 고려해야 한다. #include #include #include using namespace std; #define MAX 100001 #de.. 2024. 4. 23. 이전 1 2 3 4 5 다음
