#include <iostream>
using std::cin;
using std::cout;
int main()
{
long long A, X;
cin >> A >> X;
A %= 1000000007;
long long ans=1;
while (X > 0) {
if (X & 1) {
ans *= A;
ans %= 1000000007;
}
X >>= 1;
A *= A;
A %= 1000000007;
}
cout << ans;
return 0;
}
이 문제는 5 2 3 1 4 6에서의 "2 3 4"와 같이 1씩 증가하는 부분수열의 길이의 최댓값을 찾는 문제로 볼 수 있다.
1씩 증가하는 최장 부분수열에 해당하는 아이들을 제외한 다른 아이들을 순서에 맞춰 앞뒤로 이동시켜주면 되기 때문이다.
단순히 증가하는 부분수열만 만족하면 안 되는 이유는 아이들을 항상 맨 앞이나 맨 뒤로만 보낼 수 있기 때문이다. 예를 들어, 2 1 3 5 4 에서 1과 3, 3과 5 사이에 각각 2번 아이와 4번 아이가 한번에 들어갈 수 없기 때문이다. (답은 3번이다.)
글쓴이는 지금 서있는 아이들을 한번씩 보면서 이 아이 앞쪽에 앞번호 아이가 있었는지 확인한 배열을 저장한 뒤, 연속해서 앞번호 아이가 서있는 구간을 찾는 식으로 문제를 해결했다.
예를 들어, 10명의 아이가 1 3 2 4 6 8 5 7 10 9 와 같이 서있는 상황을 생각해보자.
각 아이 앞쪽에 앞번호 아이가 있는 아이는 2 4 5 7 9 번 아이다. 이 때, 4 5 가 가장 길게 붙어있는 부분이고, 4 앞에 있는 3번 아이까지 고려하면, 이 수열에서 1씩 증가하는 부분수열 길이의 최댓값은 3이 된다.
답을 낼 때 구한 최댓값을 전체 아이 수에서 빼는 것을 잊지 말자. 항상 문제가 요구하는 것을 제출해야 한다.
아래는 제출한 소스코드이다.
#include <iostream>
using std::cin;
using std::cout;
bool kids[1000001];
bool kidschk[1000001];
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int x;
for (int i = 1; i <= n;i++) { // 먼저 앞번호 아이가 들어왔다면 기록
cin >> x;
if (kidschk[x - 1]) kids[x] = true;
kidschk[x] = true;
}
int cnt = 0, mx = 0;
for (int i = 1;i <= n;i++) { //연속해서 앞번호아이가 있는 최대길이 구하기
if (kids[i]) {
cnt++;
if (mx < cnt) mx = cnt;
}
else cnt = 0;
}
cout << n-(mx+1);
return 0;
}
2-1) 문자열을 읽으면서, 저장된 문자와 다른 문자가 나온다면 그 저장된 문자를 현재 문자로 바꾸고 답에 10을 더한다. (맨 처음 접시를 내려놓는 경우 또는 접시를 반대로 놓는 경우)
2-2) 같은 문자가 나온다면 답에 5를 더한다. (접시를 포개어 놓는 경우)
아래는 제출한 소스코드이다.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;
int main()
{
string s;
int slen;
cin >> s;
slen = s.length();
char now = 'x'; // 초기상태: 아직 접시가 놓이지 않음
int ans = 0;
for (int i = 0;i < slen;i++) {
if (now != s[i]) { // 같지 않은 경우: 아직 접시를 안 놓았거나 접시가 반대방향
now = s[i];
ans += 10;
}
else ans += 5; // 같은 경우: 접시가 같은 방향
}
cout << ans;
return 0;
}
(1) 점을 특정 좌표로 모으기 위해 필요한 좌우방향 움직임 횟수와 상하방향 움직임 횟수는 서로 영향을 주지 않는다.
(2) 모으려는 점의 x(또는 y)좌표를 기준으로 좌우(또는 상하)에 있는 점의 개수의 차이가 최소여야한다. 이 성질을 가지고 있는 x(또는 y)좌표를 구하는 방법은 정렬을 이용하는 것이다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;
int x[100001];
int y[100001];
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
int tempx, tempy;
for (int i = 1;i <= M;i++) {
cin >> tempx >> tempy;
x[i] = tempx;
y[i] = tempy;
}
sort(x + 1, x + M+1); // 정렬
sort(y + 1, y + M+1);
int xmid = x[(M + 1) / 2]; // 원하는 성질을 가진 x좌표와 y좌표
int ymid = y[(M + 1) / 2];
int ans = 0;
for (int i = 1;i <= M;i++) { // 구한 좌표로 답 구하기
ans += abs(x[i] - xmid) + abs(y[i] - ymid);
}
cout << ans;
return 0;
}
Lagrange's four-square theorem(라그랑주의 네 제곱수 정리)에 따르면, 모든 음이 아닌 정수는 (0을 포함한) 4개의 제곱수의 합으로 표현이 가능하다.
그렇다면 어떤 수 n이 주어졌을 때 그 수를 최소 몇 개의 (0이 아닌) 제곱수의 합으로 나타낼 수 있는지는 어떻게 구할 수 있을까?
처음에는 직관으로 다음과 같은 알고리즘을 구상했다.
#1)
1) n 이하 제곱수들을 구한다. 이들은 1개의 제곱수의 합으로 나타낼 수 있다고 기록한다.
이중 n이 있다면 1을 출력한다.
2) n 이하 제곱수의 합으로 나타낼 수 있는 수(단, 1에서 구한 수 제외)들을 구한다. 이들을 제곱수의 합으로 나타내기 위해서는 최소 2개의 제곱수가 필요하다(그리고 가능하다)고 기록한다.
이중 n이 있다면 2를 출력한다.
3) 1에서 기록한 수와 2에서 기록한 수의 합으로 나타나는 수(단, 1과 2에서 구한 수 제외)들을 구한다. 이들을 제곱수의 합으로 나타내기 위해서는 최소 3개의 제곱수가 필요하다(그리고 가능하다)고 기록한다.
이중 n이 있다면 3을 출력한다.
4) 1, 2, 3에서 등장하지 않은 수는 Lagrange's four-square theorem에 따라 4개의 제곱수가 필요하다. 그러므로 4를 출력한다.
다음은 위의 알고리즘을 구현해 제출한 것이다.
#include <iostream>
using std::cin;
using std::cout;
bool nums[100001][4];
int main()
{
int n;
cin >> n;
for (int i = 1;i * i <= n;i++) {
nums[i * i][1] = true;
}
for (int i = 1;i <= n;i++) {
if (nums[i][1]) {
for (int j = i;j <= n-i;j++) {
if (nums[j][1] and !nums[i + j][1]) {
nums[i + j][2] = true;
}
}
}
}
for (int i = 1;i <= n;i++) {
if (nums[i][2]) {
for (int j = 1;j <= n-i;j++) {
if (nums[j][1] and !nums[i+j][1] and !nums[i+j][2]) {
nums[i + j][3] = true;
}
}
}
}
if (nums[n][1]) cout << 1;
else if (nums[n][2]) cout << 2;
else if (nums[n][3]) cout << 3;
else cout << 4;
}
이 알고리즘이 틀린 것은 아니나, 소요시간이 다른 사람들에 비해 매우 긴 것을 확인했다. (876ms)
그 이유를 생각해본 결과, n을 제곱수의 합으로 나타낼 수 있지 고려할 때 고려해보지 않아도 될 수까지 전부 탐색하는 것이 원인이라고 결론 내렸다. 따라서, 고려해볼 필요가 있는 수만 다루기 위해 recursion을 이용한 DP를 이용하여 다시 시도해봤다.
아래는 제출한 소스코드이다.
#include <iostream>
using std::cin;
using std::cout;
using std::min;
bool visited[100001];
int times[100001];
int dp(int n) {
int ret = 4; // 많아봤자 4개의 제곱수의 합으로 표현 가능
for (int i = 1;i * i <= n;i++) {
if (visited[n - i * i]) { //memoization: 계산했던 값은 먼저 계산한 값 반환
ret = min(ret, times[n - i * i] + 1);
}
else {//아직 안 계산해본 값이라면 계산해보기
times[n - i * i] = dp(n - i * i);
visited[n - i * i] = true;
ret = min(ret, times[n - i * i] + 1);
// ret = min("n에서 --n이하의 제곱수를 뺀 것-- 을 만드는데 필요한 제곱수의 최소 개수)
}
}
return ret;
}
int main()
{
visited[0] = true;
int n;
cin >> n;
bool chk = false;
for (int i = 1;i * i <= n;i++) {
visited[i * i] = true;
times[i * i] = 1;
if (i * i == n) {
chk = true;
}
}
if (chk) cout << 1;
else {
int ans = dp(n);
cout << ans;
}
return 0;
}