티스토리 뷰
57분만에 올솔을 해서 67등을 찍었다.
1. Double or One Thing
어떤 경우에 두 글자를 쓰고, 어떤 경우에 한 글자를 써야 할까?
두 글자를 쓰려면, 뒤에 오는 문자가 결정하는 문자보다 커야 한다.
뒤에 오는 문자가 결정하는 문자보다 작으면 한 글자를 쓰면 된다.
그러면 같은 경우에는 어떻게 해야 할까?
같은 경우에는 다다음 글자, 다다다음 글자......을 보다가 다른 문자가 나오면 결정하고, 뒤의 모든 문자가 같으면 한 글자만 쓰면 된다.
#include <bits/stdc++.h>
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
int tc = 0;
while (T--)
{
tc++;
cout << "Case #" << tc << ": ";
string s;
cin >> s;
int i;
for (i = 0; i < s.size(); i++)
{
int c = 0;
int j;
for (j = i + 1; j < s.size(); j++)
{
if (s[j] > s[i])
{
c = 1;
break;
}
else if (s[j] < s[i])
break;
}
cout << s[i];
if (c)
cout << s[i];
}
cout << '\n';
}
}2. Equal Sum
정확히 sum을 맞추려면 어떤 방법이 좋을까?
이진수를 사용하는 것이 좋을 것이다.
1, 2, 1<<29를 넣어주면 0에서 (1<<30)-1까지의 수를 다 만들어 줄 수 있고, 얼추 비슷하게 만드는 거는 저지가 준 수와 아무렇게나 출력한 수로 할 수 있다.
결국 1, 2, 1<<29만 있으면 아무렇게만 넣어도 된다는 결론이 나온다.
중복되는 수가 있어서 1틀 후 AC
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
int tc = 0;
while (T--)
{
int N;
cin >> N;
int c = 1;
int i;
int sum = 0;
vector<int>x;
for (i = 0; i < N; i++)
{
cout << c << ' ';
x.push_back(c);
sum += c;
if (c * 2 <= 1000000000)
c *= 2;
else
c++;
}
cout << '\n';
cout.flush();
vector<int>y;
for (i = 0; i < N; i++)
{
int a;
cin >> a;
if (a == -1)
return 0;
y.push_back(a);
sum += a;
}
sum /= 2;
for (i = 0; i < N; i++)
{
if (y[i] <= sum)
{
cout << y[i]<<' ';
sum -= y[i];
}
}
for (i = 0; i < N; i++)
{
if (x[N-1-i] <= sum)
{
cout << x[N-1-i] << ' ';
sum -= x[N-1-i];
}
}
cout << '\n';
cout.flush();
}
}3. Weightlifting
두 개의 운동이 있을 때, 최소 이동 수는 첫 번째 운동의 추 개수+두 번째 운동의 추 개수-2*맨 밑 부분에서 순서가 같은 추의 개수이다.
예시로 aabc와 aaacb는 4+5-2*2=5 이동이 걸린다.
우선 답을 모든 운동의 추 개수의 합*2로 해두자.
그 다음에는 각각의 추마다 최소로 이 추를 쓰는 운동에서의 추의 개수를 밑에 깔아놓고, 2*(N-1)*개수만큼 답을 줄이자.
이제 밑에 깔린 추들은 생각하지 않고 보면, 중간에는 모든 추를 비워낸 뒤에 새로 까는 곳이 있을 것이다(아니면 그 추가 밑에 깔릴 거기 때문)
여기서 모든 추를 비워내고 새로 까는 곳의 왼쪽과 오른쪽으로 문제를 나눠서 풀면 된다.
그냥 하면 지수적 시간복잡도가 나오는데, 공통으로 얼마나 깔려 있는지를 재귀적으로 풀며 저장해주고 전에 안 깔려있다고 생각할 때의 정답에서 2*(구간 크기-1)*전에 깔려 있는 개수를 빼주면 dp를 세울 수 있다.
시간 복잡도는 세제곱 혹은 네제곱이고, 나는 세제곱으로 짰다.
#include <bits/stdc++.h>
using namespace std;
int dp[101][101];
int arr[101][101];
int mi[101][101][101];
int misum[101][101];
int N, M;
int dd(int s, int e, int k)
{
if (s == e)
return 0;
if (dp[s][e] >= 0)
{
return dp[s][e] - k * (e - s);
}
int i;
for (i = s; i < e; i++)
{
dp[s][e] = max(dp[s][e], dd(s, i, misum[s][e]) + dd(i + 1, e, misum[s][e]));
}
dp[s][e] += misum[s][e] * (e - s);
return dp[s][e] - k * (e - s);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
int tc = 0;
while (T--)
{
memset(mi, 1, sizeof(mi));
memset(dp, -1, sizeof(dp));
memset(misum, 0, sizeof(misum));
cin >> N >> M;
int i,j;
int ans = 0;
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
cin >> arr[i][j];
ans += arr[i][j] * 2;
}
}
for (i = 0; i < N; i++)
{
for (j = 0; j < M; j++)
{
mi[i][i][j] = arr[i][j];
misum[i][i] += mi[i][i][j];
}
for (j = i + 1; j < N; j++)
{
int k;
for (k = 0; k < M; k++)
{
mi[i][j][k] = min(mi[i][j - 1][k], arr[j][k]);
misum[i][j] += mi[i][j][k];
}
}
}
tc++;
cout << "Case #" << tc << ": " << ans - 2 * dd(0, N - 1, 0) << '\n';
}
}