크기 n + 1짜리 bool 타입의 벡터 v를 선언하여 다음과 같이 true로 초기화시켰다.
그 다음 지울 때마다 false로 바꿔주었다.
그리고 지울 때마다 index를 1 증가시켰다. index는 몇 번째 지운 것인지를 나타낸다.
지우지 않은 숫자들 중에 가장 작은 수는 num에 저장했다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<bool> v(n + 1, true);
int index = 1;
int answer = -1;
while (true) {
int num;
for (int i = 2; i <= n; i++) {
if (v[i]) {
num = i;
v[i] = false;
if (index == k) {
answer = i;
}
index++;
break;
}
}
if (answer != -1)
break;
int a = 2;
while (a * num <= n) {
if (v[a * num]) {
v[a * num] = false;
if (index == k) {
answer = a * num;
break;
}
index++;
}
a++;
}
if (answer != -1)
break;
}
cout << answer;
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<vector<int>> v(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> v[i][j];
}
}
vector<vector<long long>> answer(n, vector<long long>(n, 0));
queue <pair<int, int>> q;
q.push(make_pair(0, 0));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
int row = cur.first;
int col = cur.second;
if (v[row][col] == 0)
continue;
if (row + v[row][col] < n) {
if (row + v[row][col] != n - 1 || col != n - 1) {
q.push(make_pair(row + v[row][col], col));
}
answer[row + v[row][col]][col]++;
}
if (col + v[row][col] < n) {
if (row != n - 1 || col + v[row][col] != n - 1) {
q.push(make_pair(row, col + v[row][col]));
}
answer[row][col + v[row][col]]++;
}
}
cout << answer[n - 1][n - 1];
return 0;
}
그래서 DP로 풀었다.
초등학교 고학년 때인지 중학교 때인지 다음과 같은 그림을 주면서
'출발점에서 도착점으로 가는 최단경로의 개수를 구하시오'
하는 문제 본 적 있을 것이다.
그 때 어떻게 풀었냐면
다들 이렇게 풀었을 것이다.
설명을 하자면
최단경로이므로 아래쪽 또는 오른쪽으로만 이동해야 한다.
따라서 위, 왼쪽의 숫자를 더한 것이 출발점에서 현 지점까지 오는 최단경로의 개수이다.
이것을 계속 반복하면 도착점까지의 최단경로의 개수를 구할 수 있다.
1890번 문제도 똑같다. 최단경로라는 말은 없지만 반드시 오른쪽이나 아래쪽으로만 이동해야 한다는 조건이 있다.
다만 거리가 이동 거리가 무조건 1이 아니라 특정 숫자만큼만 점프를 할 수 있다는 것 뿐이다.
입력으로
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0
이렇게 들어왔다고 하자.
입력값으로 들어온 것은 벡터 v에 저장해주고 동적계획법으로 풀 때 값들을 저장할 벡터는 answer이라고 했다.
초기상태는 다음과 같다.
v는 입력받은 것이고 answer[0][0]은 1을 저장해주었다.
i = 0, j = 0일 때
위쪽과 왼쪽으로 가볼 곳이 없다.
i = 0, j = 1일 때
k = 1이면
한 칸 왼쪽으로 가보면 v[0][0]은 1이 아니라 2이므로 안 된다.
왜 안 되냐? v에 저장된 값은 '몇 칸 점프할 수 있는지'이다. 따라서 v[0][0]은 2이므로 0행 0열에서는 두 칸 점프할 수 있다. 그런데 0행 0열에서 두 칸 점프해서는 0행 1열에 도달할 수 없다. 한 칸 점프해야만 도달할 수 있다. 즉 v[0][0]이 1일 때만 가능하다.
i = 0, j = 2일 때
k = 1이면
한 칸 왼쪽으로 가보면 v[0][1]은 1이 아니라 3이므로 안 된다.
k = 2이면
두 칸 왼쪽으로 가보면 v[0][0]은 2이므로 answer[0][0] 만큼을 더해준다. 즉, 1을 더해준다.
i = 0, j = 3일 때
k = 1이면
한 칸 왼쪽으로 가보면 v[0][1]은 1이 아니라 3이므로 안 된다.
k = 2이면
두 칸 왼쪽으로 가보면 v[0][1]은2가 아니라3이므로 안 된다.
k =3이면
세 칸 왼쪽으로 가보면 v[0][1]은3이 아니라2이므로 안 된다.
i = 1, j = 0일 때
k = 1이면
한 칸 위쪽으로 가보면 v[0][0]은 1이 아니라 2이므로 안 된다.
i = 1, j = 1일 때
k = 1이면
한 칸 위쪽으로 가보면 v[0][1]은 1이 아니라 3이므로 안 된다.
한 칸 왼쪽으로 가보면 v[1][0]은 1이므로 answer[1][0] 만큼을 더해준다. 즉, 0을 더해준다.
i = 1, j = 2일 때
k = 1이면
한 칸 위쪽으로 가보면 v[0][2]은 1이 아니라 3이므로 안 된다.
한 칸 왼쪽으로 가보면 v[1][1]은 1이 아니라 2이므로 안 된다.
k =2이면
두 칸 왼쪽으로 가보면 v[1][0]은 2가 아니라 1이므로 안 된다.
i = 1, j = 3일 때
k =1이면
한 칸 위쪽으로 가보면 v[0][3]은 1이므로 answer[0][3] 만큼을 더해준다. 즉, 0을 더해준다.
한 칸 왼쪽으로 가보면 v[1][2]은 1이므로 answer[1][2] 만큼을 더해준다. 즉, 0을 더해준다.
k =2이면
두 칸 왼쪽으로 가보면 v[1][1]은 2이므로 answer[1][1] 만큼을 더해준다. 즉, 0을 더해준다.
k =3이면
세 칸 왼쪽으로 가보면 v[1][0]은 3이 아니라 1이므로 안 된다
i = 2, j = 0일 때
k =1이면
한 칸 위쪽으로 가보면 v[1][0]은 1이므로 answer[1][0] 만큼을 더해준다. 즉, 0을 더해준다.
k =2이면
두 칸 위쪽으로 가보면 v[0][0]은 2이므로 answer[0][0] 만큼을 더해준다. 즉, 1을 더해준다.
i = 2, j = 1일 때
k =1이면
한 칸 위쪽으로 가보면 v[1][1]은1이 아니라2이므로 안 된다.
한 칸 왼쪽으로 가보면 v[2][0]은 1이므로 answer[2][0] 만큼을 더해준다. 즉, 1을 더해준다.
k =2이면
두 칸 위쪽으로 가보면 v[0][1]은 2가 아니라 3이므로 안 된다.
i = 2, j = 2일 때
k =1이면
한칸 위쪽으로 가보면 v[1][2]는1이므로 answer[1][2] 만큼을 더해준다. 즉, 0을 더해준다.
한 칸 왼쪽으로 가보면 v[2][0]은 1이 아니라2이므로 안 된다.
k =2이면
두 칸 위쪽으로 가보면 v[0][2]은 2가 아니라 3이므로 안 된다.
두 칸 왼쪽으로 가보면 v[2][0]은 2가 아니라 1이므로 안 된다.
i = 2, j = 3일 때
k = 1이면
한칸 위쪽으로 가보면 v[2][0]은 1이 아니라3이므로 안 된다.
한칸 왼쪽으로 가보면 v[2][0]은 1이 아니라3이므로 안 된다.
k = 2이면
두칸 위쪽으로 가보면 v[2][0]은2가 아니라1이므로 안 된다.
두칸 왼쪽으로 가보면 v[2][1]은2이므로 answer[2][1] 만큼을 더해준다. 즉, 1을 더해준다.
k = 3이면
세칸 왼쪽으로 가보면 v[2][0]은 3이 아니라1이므로 안 된다.
i = 3, j = 0일 때
k = 1이면
한칸 위쪽으로 가보면 v[2][0]은1이므로 answer[2][0] 만큼을 더해준다. 즉, 1을 더해준다.
k = 2이면
두칸 위쪽으로 가보면 v[1][0]은2가 아니라1이므로 안 된다.
k = 3이면
세칸 위쪽으로 가보면 v[0][0]은 3이 아니라2이므로 안 된다.
i = 3, j = 1일 때
k = 1이면
한칸 위쪽으로 가보면 v[2][1]은 1이 아니라2이므로 안 된다.
한칸 왼쪽으로 가보면 v[3][0]은 1이 아니라3이므로 안 된다.
k = 2이면
두칸 위쪽으로 가보면 v[1][1]은2이므로 answer[1][1] 만큼을 더해준다. 즉, 0을 더해준다.
N!을 직접 구하는 것은 숫자가 기하급수적으로 커지므로 직접 구하면 아마 오버플로우가 날 것이다.
따라서 다른 방법을 사용했다.
어떤 숫자가 뒤에서부터 0이 1개 나온다는 것은 10의 배수라는 것이다.
어떤 숫자가 뒤에서부터 0이 연속으로 2개 나온다는 것은 100의 배수라는 것이다.
어떤 숫자가 뒤에서부터0이 연속으로 3개 나온다는 것은 1000의 배수라는 것이다.
그러므로 소인수분해를 하여 2와 5의 개수를 세어주면 된다.
2가 6개, 5가 3개면 10을 3개 만들 수 있다.
2가 100개이더라도 5가 3개이면 10을 3개만 만들 수 있다.
2가 5개, 5가 100개여도 10을 5개 만들 수 있다.
N부터 N-1, N-2, N-3, ... , 2, 1까지 각각을 소인수분해를 하여 2의 개수를 twoCount에, 5의 개수를 fiveCount에 저장하고 twoCount와 fiveCount 중에 더 작은 값이 10을 몇 개 만들 수 있는지를 뜻하므로 min(twoCount, fiveCount)를 출력하도록 했다.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int twoCount = 0;
int fiveCount = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num % 2 == 0) {
num /= 2;
twoCount++;
}
while (num % 5 == 0) {
num /= 5;
fiveCount++;
}
}
cout << min(twoCount, fiveCount);
return 0;
}
머리 안 쓰고 문제에 나와있는 그대로 재귀로 풀었었는데 시간제한이 0.5초로 변경되면서 시간초과로 결과가 바뀌었다.
그래서 다시 풀었다.
#include <iostream>
#include <cmath>
using namespace std;
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int n, r, c;
cin >> n >> r >> c;
n = pow(2, n);
int index = 0;
while (true) {
if (n == 1) {
break;
}
if (r < n / 2 && c < n / 2) {
}
else if (r < n / 2 && c >= n / 2) {
c -= n / 2;
index += pow(n / 2, 2);
}
else if (r >= n / 2 && c < n / 2) {
r -= n / 2;
index += pow(n / 2, 2) * 2;
}
else {
r -= n / 2;
c -= n / 2;
index += pow(n / 2, 2) * 3;
}
n /= 2;
}
cout << index;
return 0;
}
