https://www.acmicpc.net/problem/10350
생애 첫 루비문제입니다.
애드혹 문제라서 그런지 백준 게시판이나 블로그에서 아이디어를 얻지 않았다면 절대 손도 못댈거같은 그런 문제였습니다..
제가 힌트를 얻은건 1 ~ N번째 수를 계속 이어붙였을 때 음수 누적합이 나오는 갯수를 구하는 것이었습니다.
사실상 문제의 모든것 이었습니다..
아무튼 저는 누적합으로 접근했고, 각 은행들은 원형으로 배치되어 있기때문에 1 ~ N이 아닌 1 ~ 2N의 누적합으로 구해줍니다.
그리고 1, 2, 3, ... N에서 시작하여 N개의 수를 계속 이어붙일 때의 누적합들 중에 음수가 몇번 나오는지 카운팅하면 그게 답입니다.
4
1 -2 -1 3예시로 설명드리면
처음 1번부터 누적합을 쭉 구하면
1 -1 -2 1 / 2 0 -1 2 / 3 1 0 3이렇게 되고, 음수의 갯수는 3개입니다.
그리고 이후에 배열을 계속 이어도 음수가 나오지 않습니다.
그 다음 2번부터 누적합을 구하면
x -2 -3 0 1 / -1 -2 1 2 / 0 -1 2 3이렇게 되고, 음수의 갯수는 5개입니다.
다음 3번부터 누적합을 구하면
x x -1 2 3 1 / 0 3 4 2 / 1 4 5 3이렇게 되고, 음수의 갯수는 1개입니다.
마지막 4번부터 누적합을 구하면
x x x 3 4 2 1 / 4 5 3 2 / 5 6 4 3이렇게 되고, 음수의 갯수는 0개입니다.
위에서 구한 갯수들을 전부 더하면 9개가 됩니다.
이 과정에서 규칙을 하나 찾을 수 있습니다.
우선 문제에서 입력으로 주어지는 수를 모두 더하면 양수라고 했습니다.
그리고 각 시작 지점을 i번이라고 했을 때 i번부터 N개의 누적합은 무조건 양수입니다.
제가 4개씩 끊은 구간들을 보시면 1번 구간의 수들에서 +1한 값들이 2번 구간이 되어 있습니다.
그리고 2번 구간에서 +1를 하면 3번 구간이 됩니다.
그 +1은 배열의 전체 누적합이 되고, 음수의 갯수는 음수 누적합 / 전체 누적합이 되는것을 알 수 있습니다.
계산하면 실수가 나오기 때문에 double형으로 바꿔주셔야 하고, 나머지는 무조건 올림 연산을 해야합니다.
이 방식으로 접근하시면 로직 자체는 간단하게 구현하실 수 있습니다.
이 문제는 이 방식을 생각해내는것 자체가 정말 어렵다는 것을 느꼈습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <iostream>
#include <cmath>
#define MAX 20001
using namespace std;
typedef long long ll;
int dp[MAX];
int N;
void init() {
for (int i = 1; i <= (N << 1); i++) {
dp[i] += dp[i - 1];
}
}
void func() {
init();
ll ret = 0;
for (int i = 1; i <= N; i++) {
for (int j = i; j < N + i; j++) {
if (dp[j] - dp[i - 1] >= 0) continue;
ret += (ll)ceil((double)(-dp[j] + dp[i - 1]) / (double)(dp[N + i - 1] - dp[i - 1]));
}
}
cout << ret << '\n';
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> dp[i];
dp[i + N] = dp[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > ad-hoc' 카테고리의 다른 글
| boj 14370 전화번호 수수께끼 (Large) (0) | 2024.08.06 |
|---|---|
| boj 21316 스피카 (0) | 2024.08.05 |
| boj 5527 전구 장식 (0) | 2024.07.30 |
| boj 14864 줄서기 (0) | 2024.07.26 |
| boj 2381 최대 거리 (0) | 2024.07.25 |