백준 BOJ 풀이 (IGRUS Newbie Programming Contest 일부 포함)
백준 BOJ 25711번 : 인경산
문제 난이도 : Gold V
알고리즘 분류 : 누적 합
2차원 좌표 상의 N개의 점이 주어지고, 어떤 인접한 구간의 두 점 사이를 이동할 때 필요한 에너지는 내리막길일 경우 거리에 해당, 평지일 경우 거리의 2배, 오르막길일 경우 거리의 3배라고 할 때 M개의 쿼리에 대해 두 지점 사이의 필요한 에너지들을 구하는 문제이다.
쿼리 문제이므로 O(1)이나 O(log N)과 같이 짧은 시간에 쿼리를 처리할 수 있어야 한다.
이 문제에서는 누적 합을 이용하여, 맨 왼쪽 지점에서부터 특정 지점까지 이동하는데 필요한 에너지들의 목록을 구해둔다.
반대로, 맨 오른쪽 지점에서부터 특정 지점까지 이동하는데 필요한 에너지들의 목록도 구해둔다.
각각의 값들은 위에서 정의한 식대로 구해주면 된다.
이제 왼쪽 i번 지점에서 오른쪽 j번 지점으로 이동하는데 필요한 에너지는 (i < j) u[j] - u[i]와 같이 O(1)에 구할 수 있고, 오른쪽 i번 지점에서 왼쪽 j번 지점으로 이동하는데 필요한 에너지 (i > j) 역시 w[j] - w[i]와 같이 구할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { double x, y; };
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<s> v(N);
for(int i=0; i<N; i++) cin >> v[i].x;
for(int i=0; i<N; i++) cin >> v[i].y;
vector<double> u(N), w(N);
for(int i=1; i<N; i++) {
if(v[i].y < v[i-1].y)
u[i] = u[i-1] + sqrt(pow(v[i].x - v[i-1].x, 2) + pow(v[i].y - v[i-1].y, 2));
else if(v[i].y == v[i-1].y)
u[i] = u[i-1] + sqrt(pow(v[i].x - v[i-1].x, 2) + pow(v[i].y - v[i-1].y, 2)) * 2;
else if(v[i].y > v[i-1].y)
u[i] = u[i-1] + sqrt(pow(v[i].x - v[i-1].x, 2) + pow(v[i].y - v[i-1].y, 2)) * 3;
}
for(int i=N-2; i>=0; i--) {
if(v[i].y < v[i+1].y)
w[i] = w[i+1] + sqrt(pow(v[i].x - v[i+1].x, 2) + pow(v[i].y - v[i+1].y, 2));
else if(v[i].y == v[i+1].y)
w[i] = w[i+1] + sqrt(pow(v[i].x - v[i+1].x, 2) + pow(v[i].y - v[i+1].y, 2)) * 2;
else if(v[i].y > v[i+1].y)
w[i] = w[i+1] + sqrt(pow(v[i].x - v[i+1].x, 2) + pow(v[i].y - v[i+1].y, 2)) * 3;
}
cout << fixed;
cout.precision(4);
while(M--) {
int a, b; cin >> a >> b;
if(a < b) cout << u[b-1] - u[a-1] << "\n";
else cout << w[b-1] - w[a-1] << "\n";
}
}
백준 BOJ 25708번 : 만남의 광장
문제 난이도 : Silver II
알고리즘 분류 : 누적 합
N x M 크기의 정수 배열이 주어지고, 이들 중에서 가로와 세로로 2줄씩을 제거하여 도로를 만들 때, 도로 위에 써 있는 숫자들의 합에 네 도로가 감싸는 잔디의 개수를 더한 값의 최댓값을 구하는 문제이다.
네 도로를 결정할 때 가능한 모든 경우를 해보면 O(N^2 M^2)가 되는데, N과 M이 작아 이 정도까지는 돌아간다.
문제는 도로 위에 써 있는 숫자들을 빨리 더하는 방법인데 이것은 N개의 도로와 M개의 도로에 대해 각각의 합을 미리 구해두면 된다.
시간 복잡도는 위에서 언급한대로 O(N^2 M^2)이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> v(N, vector<int>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
vector<int> u(N), w(M);
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) u[i] += v[i][j];
for(int i=0; i<M; i++)
for(int j=0; j<N; j++) w[i] += v[j][i];
int ans = INT_MIN;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++)
for(int k=i+1; k<N; k++)
for(int l=j+1; l<M; l++) {
int sum = u[i] + w[j] + u[k] + w[l]
- v[i][j] - v[k][l] - v[i][l] - v[k][j]
+ (k-i-1) * (l-j-1);
ans = max(ans, sum);
}
cout << ans << "\n";
}
백준 BOJ 25710번 : 점수 계산
문제 난이도 : Silver II
알고리즘 분류 : 브루트포스 알고리즘
1 ~ 999 사이의 수 10만개가 주어질 때, 두 정수를 곱하여 얻어진 수의 각 자릿수를 더해 얻을 수 있는 최댓값을 구하는 문제이다.
N이 10만 이하로 O(N^2)에 돌리면 시간 초과가 발생하지만, 1 ~ 999 사이의 수만 입력되므로 이들 중에서 존재하는 수들에 대해서만 검사해보면 된다.
이렇게 할 경우 시간 복잡도는 O(1000^2)로 매우 작다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(1000);
for(int i=0; i<N; i++) {
int x; cin >> x;
v[x]++;
}
vector<int> u;
for(int i=1; i<=999; i++) {
if(v[i] == 1) u.push_back(i);
else if(v[i] >= 2) {
u.push_back(i);
u.push_back(i);
}
}
int ans = 0;
for(int i=0; i<u.size(); i++)
for(int j=i+1; j<u.size(); j++) {
int tmp = u[i] * u[j];
int sum = 0;
while(tmp > 0) {
sum += tmp % 10;
tmp /= 10;
}
ans = max(ans, sum);
}
cout << ans << "\n";
}
백준 BOJ 25709번 : 1 빼기
문제 난이도 : Silver IV
알고리즘 분류 : 그리디
주어진 수에 대해, 가지고 있는 수에서 1을 빼거나 또는 어떤 자리가 1의 값을 가질 때 해당 자리를 지우는 연산을 거쳐 0으로 만들기 위해 필요한 최소 연산 횟수를 구하는 문제이다.
우선적으로 높은 자릿수에 있는 1을 먼저 지우고, 만약 1이 없다면 1을 감소시키는 연산을 반복하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int ans = 0;
while(true) {
if(N == 0) break;
string tmp = to_string(N);
int idx = -1;
for(int i=0; i<tmp.length(); i++)
if(tmp[i] == '1') {
idx = i;
break;
}
if(idx != -1) {
tmp = tmp.substr(0, idx) + tmp.substr(idx+1, tmp.length()-(idx+1));
N = 0;
for(int i=0; i<tmp.length(); i++) N = N * 10 + tmp[i] - '0';
}
else N--;
ans++;
}
cout << ans << "\n";
}
백준 BOJ 25706번 : 자전거 묘기
문제 난이도 : Silver V
알고리즘 분류 : DP
각 위치에서의 점프대의 높이에 해당하는 N개의 수가 주어졌을 때, 각 위치에서 시작했을 때 밟게 되는 칸의 수를 구하는 문제이다.
역순으로 dp에 값들을 저장하면서 뒤의 dp 값들을 참조하여 답을 구해주면 된다.
( i ) 만약 시작 칸의 점프대 높이가 0이라면 dp[i] = dp[i+1] + 1이다.
( ii ) 시작 칸에서 점프대를 밟고 이동한 위치가 끝 또는 그 이상일 경우 dp[i] = 1이다.
( iii ) 위의 두 경우가 아니라면 dp 값은 점프대를 밟고 이동한 위치에서의 dp 값 + 1이 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<int> u(N);
u[N-1] = 1;
for(int i=N-2; i>=0; i--) {
if(v[i] == 0) u[i] = u[i+1] + 1;
else if(i + v[i] + 1 >= N) u[i] = 1;
else u[i] = u[i + v[i] + 1] + 1;
}
for(int i=0; i<N; i++) cout << u[i] << " ";
cout << "\n";
}
백준 BOJ 16980번 : Bitaro the Brave
문제 난이도 : Silver III
알고리즘 분류 : 누적 합
N x M 문자 배열이 주어졌을 때, 왼쪽 위에는 'J', 오른쪽 위에는 'O', 왼쪽 아래에는 'I'인 직사각형의 개수를 구하는 문제이다.
오른쪽 아래에서부터 왼쪽 위로 검사하면서 J가 나올 때마다 지금까지 오른쪽에 나타난 O의 개수와 아래에 나타난 I의 개수의 곱만큼을 답에 더해주는 과정을 반복하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<char>> v(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
vector<int> u(M);
int ans = 0;
for(int i=N-1; i>=0; i--) {
int x = 0;
for(int j=M-1; j>=0; j--) {
if(v[i][j] == 'J') ans += x * u[j];
else if(v[i][j] == 'O') x++;
else if(v[i][j] == 'I') u[j]++;
}
}
cout << ans << "\n";
}
백준 BOJ 2208번 : 보석 줍기
문제 난이도 : Gold II
알고리즘 분류 : DP
길이 N인 수열에서, 길이가 M 이상인 구간에 대해 최대 구간 합을 구하는 문제이다.
먼저 구간 합 배열을 만들어준다.
이제 i = M, 최소 구간합은 0부터 검사하면서 0 ~ i까지의 구간 합에서 0 ~ i-M 구간의 최소 구간합을 빼주는 과정을 i에 대해 반복해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N+1);
for(int i=1; i<=N; i++) {
int x; cin >> x;
v[i] = v[i-1] + x;
}
int ans = 0, Min = 0;
for(int i=M; i<=N; i++) {
Min = min(Min, v[i-M]);
ans = max(ans, v[i] - Min);
}
cout << ans << "\n";
}