백준 마라톤 (코스88)
(8/8)
마라톤 연속 달리기
Attractive Flowers (19805, S5)
풀이
n번에 걸쳐서 꽃의 개수가 주어진다
각 턴당 홀수개의 꽃을 잡아야하고, 다 합쳐서 홀수개의 꽃이 되어야하므로
큰 순서로 정렬하고, 홀수개의 꽃들을 집어서 모두 더해주면 된다.
n이 짝수면 마지막 항은 더해주지 않는다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n;
vector<ll> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
sort(v.rbegin(), v.rend());
for(int i=0;i<n;i++){
if(n%2==0){
if(i==n-1)continue;
}
if(v[i]%2)ans+=v[i];
else ans+=(v[i]-1);
}
cout << ans;
return 0;
}
B번 Пробки (19773, S1)
풀이
최소한의 운전자들이 화를 내도록 도로에 있는 차를 보내줘야 한다.
우선 1명씩은 반드시 보내야하므로 각 차로에 1씩 투자를 하고
ang()라는 그 차로의 운전자들의 화를 계산하는 함수를 만든다.
그러고서 priority_queue를 통해 가장 화가 많이 감소하는 차로에 넣어주면 된다.
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
ll ang(ll a, ll b){
ll ret=0;
while((a-=b)>0){
ret+=(a*(a-1)/2);
}
return ret;
}
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n >> k;
vector<ll> v(n);
for(int i=0;i<n;i++)cin>>v[i];
vector<ll> ansv(n, 1);
k-=n; //일단 1씩 다 줘.
priority_queue<P> pq;
for(int i=0;i<n;i++){
ll aa=ang(v[i], 1);
ll bb=ang(v[i], 2);
pq.push({aa-bb, i});
}
while(k-->0){
int idx=pq.top().second;
pq.pop();
ansv[idx]++;
ll aa=ang(v[idx], ansv[idx]);
ll bb=ang(v[idx], ansv[idx]+1);
pq.push({aa-bb, idx});
}
for(int i=0;i<n;i++){
ans+=ang(v[i], ansv[i]);
//cout << ans << '\n';
}
cout << ans<<'\n';
string sp="";
for(int i=0;i<n;i++){
cout << sp << ansv[i];
sp=' ';
}
return 0;
}
C번 Bee Maja (6575, S1)
풀이
관찰과 구현 문제이다.
1을 0번째 껍질이라고 보고 쭉 1, 2, … n번째 껍질이라고 하자.
숫자가 늘어나는 규칙은 왼쪽 위, 위, 오른쪽 위, 오른쪽 아래, 아래, 왼쪽 아래 순이다.
이 때 아래는 n+1번 움직이고, 왼쪽 아래는 n-1번 움직이며, 나머지는 n번 움직인다.
이것을 dx, dy, cha 배열을 통해서 구현했다.
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
46
47
48
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
vector<P> v(100005);
//1, 7, 19에서 밑으로 내려감 (0, +1)
//6각 패턴 (-1, 0), (0, -1), (+1, -1), (+1, 0), (0, +1), (-1, +1)
v[1]={0,0};
int ddx[6]={-1, 0, 1, 1, 0, -1};
int ddy[6]={0, -1, -1, 0, 1, 1};
int cha[6]={0, 0, 0, 0, 1, -1}; //5번째는 1번 더 하고, 6번짼 한번 덜함
int idx=0;
int cur=0;
int gi=0;
for(int i=2;i<=100000;i++){
cur++;
while(cur>gi+cha[idx]){
idx++;
idx%=6;
}
v[i].first=v[i-1].first+ddx[idx];
v[i].second=v[i-1].second+ddy[idx];
if(cur==gi+cha[idx]){
cur=0;
idx++;
idx%=6;
if(idx==5){
gi++;
}
}
}
while(cin>>n){
cout << v[n].first << ' ' << v[n].second << '\n';
}
return 0;
}
D번 템포럴 그래프 (25953, G3)
풀이
DP로 시간마다 시작점에서 갈 수 있는 위치들의 최소 거리를 업데이트 해주면 된다.
그래프가 양방향이라는 것을 놓쳐서 삽질을 하다 겨우 풀었다.
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
46
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n >> t >> m; //정점 개수, 시간, 시간 마다 간선 개수고
int st, to;
cin >> st >> to;
vector<vector<ll>> dst(t+1, vector<ll>(n, 1e16));
dst[0][st]=0;
for(int i=1;i<=t;i++){
for(int j=0;j<n;j++){
dst[i][j]=min(dst[i][j], dst[i-1][j]);
}
for(int j=0;j<m;j++){
cin >> a >> b >> c; //길이랑 가중치
if(dst[i-1][a]<1e16){
dst[i][b]=min({dst[i][b], dst[i-1][a]+c});
}
if(dst[i-1][b]<1e16){
dst[i][a]=min(dst[i][a], dst[i-1][b]+c);
}
}
}
// for(int i=1;i<=t;i++){
// for(int j=0;j<n;j++){
// cout << dst[i][j]<<' ';
// }cout<<'\n';
// }
if(dst[t][to]==1e16)cout<<"-1\n";
else cout << dst[t][to];
return 0;
}
E번 Cutting Banknotes (21386, G3)
풀이
지폐의 개수 각 값, 만드려는 돈의 값이 주어진다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=1;
ll r;
cin >> t;
while(t-->0){
double dd;
cin >> dd;
d=int(dd*100+0.5);
cin >> n;
vector<int> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
v[i]*=100;
}
a=v[0];
for(int i=1;i<n;i++){
a=gcd(a, v[i]);
}
while(a%2==0)a/=2;
while(d%2==0)d/=2;
if(d%a)cout<<"no\n";
else cout<<"yes\n";
}
return 0;
}
F번 등비수열 (15712, G2)
풀이
처음에는 등비수열의 합 공식을 사용해 a(r^n-1)/r-1 을 사용하면 쉽게 될 것 같았으나
moduler 연산이 있기 때문에 나누기를 적용할 수 없다.
moduler inverse를 하기에도 mod가 소수가 아니기에 안 풀릴 것 같았다.
그래서 그냥 식 자체를 뜯어보다 보니 패턴이 있었다.
1
1+r+r^2+r^3+r^4+r^5
라는 식은
1
(1+r^3)(1+r+r^2)
으로 변형이 가능하다.
그러면 r^n은 분할 정복을 통해서 빠르게 계산이 가능하고
식을 쪼개는 것도 분할 정복을 통해서 가능하므로 2번의 분할 정복을 해주면 된다.
이 때 식을 쪼갤 때 홀수면 따로 power를 통해 더해서 계산해줘야 했고
moduler 계산을 곳곳에 하지 않으면 overflow가 나서 신경써야 했다.
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
46
47
48
49
50
51
52
53
54
55
56
ll power(ll r, ll n, ll mod){
ll res=1;
r%=mod;
while(n>0){
if(n%2==1){
res*=r;
res%=mod;
}
r*=r;
r%=mod;
n/=2;
}
return res;
}
ll sol(ll r, ll n, ll mod){
if(n==1)return 1;
if(n%2==1){
return (power(r, n-1, mod)+sol(r, n-1, mod))%mod;
}
else{
return (((1+power(r, n/2, mod))%mod) * sol(r, n/2, mod))%mod;
}
}
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
ll r;
cin >> a >> r >> n >> mod;
//a(1+r+r^2+...r^(n-1))
if(r==1){
cout << ((a*n)%mod);
return 0;
}
k=sol(r, n, mod);
a%=mod;
//cout << power(r, n, 100000000);
cout << (k*a)%mod;
return 0;
}
G번 좋은 부분 문자열의 개수 (13507, G1)
풀이
아이디어는 금방 생각났는데 자료구조 때문에 헤맸다.
문자열의 최대 길이가 1500자이므로 연속된 모든 부분 문자열의 개수의 최대는 약 1500*1500이다.
그렇기에 누적합으로 각 문자열의 시작 끝 index에 따라 나쁜 알파벳의 개수를 구할 수 있고
개수도 많지 않기에 set을 통해서 중복을 제거할 수 있을 줄 알았다.
하지만 바로 전부 계산하기에는 메모리 초과가 난다.
그래서 트라이 자료구조를 구현해야만 하는가.. 생각을 했지만 set을 통한 트릭을 사용하면 가능했다.
모든 문자열을 같은 set에 저장을 하면 문제가 생기지만 트라이의 아이디어를 빌려 부분 문자열의
첫 알파벳에 따라서 set을 바꿔주면 메모리가 1/26 수준으로 줄어들기 때문에 가능하다.
대신 시간 복잡도가 26배 증가하긴 하지만 그정도는 충분히 돌아가기에 반복문을 하나 더 넣어서
각 부분 문자열이 a~z로 시작하는지 보고, 쭉 돌며 다 구했으면 set을 초기화하는 방식을 사용했다.
알아두면 좋은 트릭인 것 같다.
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
string s, bs;
cin >> s;
cin >> bs;
int sz=s.size();
vector<bool> bad(26, 0);
for(int i=0;i<26;i++){
if(bs[i]=='0')bad[i]=1;
}
vector<int> nu(sz+1, 0);
for(int i=0;i<sz;i++){
if(bad[s[i]-'a']){
nu[i+1]=nu[i]+1;
}
else nu[i+1]=nu[i];
}
// for(int i=0;i<=sz;i++){
// cout<< nu[i] << ' ';
// }cout<<'\n';
cin >> k;
set<string> st;
string tmp="";
for(int x=0;x<26;x++){
for(int i=0;i<sz;i++){
tmp="";
if(s[i]!='a'+x)continue;
for(int j=i+1;j<=sz;j++){
if(nu[j]-nu[i]<=k){
tmp.push_back(s[j-1]);
st.insert(tmp);
//cout << tmp << '\n';
}
else break;
}
}
//cout << x << ' ' << st.size() << '\n';
ans+=st.size();
st.clear();
}
cout<< ans;
return 0;
}
H번 미네크래프트 (15708, P5)
풀이
총 시간과 돌을 캐는 시간, 돌 하나당 캐는 시간이 주어진다.
관찰을 해보면 이동하는 시간을 포함해 돌을 캐는 시간이 가장 짧은 것을 캐는 것이 이득이며
그렇게 이동을 해서 i번쨰 돌을 캤다면 그 돌보다 앞에 있는 돌의 이동 시간은 사라진다.
하지만 우선순위 큐를 사용해도 이동할 때마다 앞에 있는 돌의 이동 시간을 업데이트 하는 것이
구현할 수 없는 것 같아서 에디토리얼을 봤다.
문제를 뒤집어서 생각하면 i번쨰 있을 때 캘 수 있는 가장 많은 돌의 개수를 구하면 되는 문제였다.
i번째까지 왔을 때 돌들의 합을 관리하며, 만약 캘 수 없는 크기가 되면 가장 큰 돌을 빼준다.
그렇게 i=1부터 n까지 pq를 통해 계산을 해서 가장 많은 돌의 개수를 캘 수 있었을 때가 답이다.
1
while(!pq.empty()&&tt+i*t>m)
이 부분의 while을 if로 바꿔도 된다는 질문글이 있어서 확인을 해봤는데 정말 된다.
디버깅을 해보면 풀이를 정확히 구현한 것은 while이라는 생각은 드는데, 어차피 i가 증가할때마다
늘어날 수 있는 돌의 개수도 최대 1개이기 때문에 if를 통해서 업데이트를 해도 같은 결과가 나온다.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n >> m >> t;
priority_queue<ll> pq;
vector<ll> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
ll tt=0;
for(int i=0;i<n;i++){
if(m-t*i<=0)break;
tt+=v[i];
pq.push(v[i]);
while(!pq.empty()&&tt+i*t>m){
tt-=pq.top();
pq.pop();
}
ans=max(ans, (ll)pq.size());
//cout << "!" << pq.size() << '\n';
}
cout << ans;
return 0;
}