생각하는 과정이 필요한 문제였습니다. 각각의 결과값들을 순차대로 구하다 보면 규칙을 찾을 수 있습니다.
점화식만 구하면 쉽게 구현할 수 있는 문제였습니다.
n = 5 k = 4 의 예제를 살펴보겠습니다.
표
0
1
2
3
4
5
dp[1]
0
0
0
0
0
1
dp[2]
1
1
1
1
1
1
dp[3]
6
5
4
3
2
1
dp[4]
21
15
10
6
3
1
dp[k]은 dp[k][0] ~ dp[k][n]의 합이 됩니다. 그리고 각각의 dp[k][i] 는 dp[k-1][i] ~ dp[k-1][n] 까지의 합이 됩니다.
비교적 쉽게 점화식을 구할 수 있습니다.
그래서 ex) 5 4의 결과값은 21+15+10+6+3+1 = ? 이 되겠죠 ㅎㅎ
그다음으로 주의하셔야 할 것은 %연산을 해주는 위치와 숫자 범위입니다. 매번 dp[k-1][i] ~ dp[k-1][n]의 연산마다 %1000000000연산을 해줘도 해당문제에서는 상관없습니다. 하지만 조금더 컴팩트 하게 코딩하기 위해서 dp[k][i] 에서만 %1000000000연산을 해주고 싶었습니다.
근데 만약 dp[k-1] 의 합이 다 10^9를 초과해서 오버플로우가 난다면, 에러가 날 수 밖에 없습니다. 그래서 long long 을 사용해서 배열을 구현했습니다.
아래는 정답코드입니다. :) 직접 표를 작성해보시고 점화식을 시그마형태로 구하고 구현해보세요! 화이팅
#include <iostream>
using namespace std;
long long dp[202][202] = { 0 };
int n, k;
long long result = 0;
int main() {
cin >> n >> k;
dp[1][n] = 1; // 초기값 설정
for (int i = 1; i <= k; i++) {
for (int j = 0; j <= n; j++) {
for (int u = j; u <= n; u++)
dp[i][j] += dp[i - 1][u];
dp[i][j] %= 1000000000;
}
}
for (int i = 0; i <= n; i++)
result += dp[k][i];
result %= 1000000000;
cout << result << endl;
}
bool cmp(info a, info b) {
if (a.korean > b.korean) //1
return true;
else if(a.korean == b.korean){
if (a.english < b.english) return true; //2
else if(a.english == b.english){
if (a.math > b.math) return true; //3
else if(a.math == b.math) {
if (a.name < b.name)return true; //4
}
}
}
return false;
}
처음에 시간초과가 났습니다. n = 100000 이고 sort 함수를 O(nlgn) 이기때문에 정렬의 문제는 아니였습니다.
endl << 이 너무 많은 시간을 잡아먹어서 에러가 났었습니다. endl는 버퍼를 flush하는 역할을 겸하기 때문에 위 처럼 많은 출력을 해야해서 endl이 많이 사용될때는 endl사용을 지양하고 '\n'을 사용해야 합니다.
정답코드입니다.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct info {
string name;
int korean;
int english;
int math;
};
info arr[100001];
int n = 0;
/*
국어 점수가 감소하는 순서로
국어 점수가 같으면 영어 점수가 증가하는 순서로
국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)
*/
bool cmp(info a, info b) {
if (a.korean > b.korean) //1
return true;
else if(a.korean == b.korean){
if (a.english < b.english) return true; //2
else if(a.english == b.english){
if (a.math > b.math) return true; //3
else if(a.math == b.math) {
if (a.name < b.name)return true; //4
}
}
}
return false;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i].name >> arr[i].korean >> arr[i].english >> arr[i].math;
sort(arr, arr + n, cmp);
for (int i = 0; i < n; i++)
cout << arr[i].name <<'\n';
}
우선 시뮬레이션 문제로 인식했습니다. 문제에서 요구하는 조건 그대로 이동하면서 결과값을 도출하게 끔 구현을 했습니다.
문제조건인
현재 구슬이 놓인 노드의 자식이 없다면 그 자리에서 멈춘다.
1을 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 한 개라면 해당 자식 노드로 떨어진다.
1, 2를 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 두 개라면,
현재 노드의 왼쪽 서브트리에 담긴 모든 구슬의 수 <= 오른쪽 서브트리에 담긴 모든 구슬의 수일 경우, 왼쪽 자식 노드로 떨어진다.
그 외의 경우에는 오른쪽 자식 노드로 떨어진다.
1~3번의 조건을 다시 체크하고 되풀이한다.
를 생각하면서 구현한 답입니다.
#include <iostream>
using namespace std;
int n, u, v;
long long k;
int result = 0;
struct node {
int left = 0;
int right = 0;
};
node arr[200001];
int cnt[200001] = { 0 };
int left_cnt, right_cnt;
void add_cnt(int current,int direction) {
if (arr[current].left == 0 && arr[current].left == 0) {
if (direction == 0)
left_cnt += cnt[current];
else
right_cnt += cnt[current];
return;
}
if (arr[current].left != 0) add_cnt(arr[current].left,direction);
if (arr[current].right != 0) add_cnt(arr[current].right, direction);
}
void action(int current,int i) {
//1
if (arr[current].left == 0 && arr[current].left == 0) {
cnt[current]++;
result = current;
return;
}
//2
else if ((arr[current].left != 0 && arr[current].right == 0)) action(arr[current].left,i);
else if ((arr[current].left == 0 && arr[current].right != 0)) action(arr[current].right,i);
//3
else if (arr[current].left != 0 && arr[current].left != 0) {
/*
left_cnt = 0, right_cnt = 0;
add_cnt(arr[current].left,0);
add_cnt(arr[current].right,1);
if(left_cnt <= right_cnt) action(arr[current].left);
else action(arr[current].right);
*/
if(i%2) action(arr[current].left,i/2 +1);
else action(arr[current].right, i/2);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> u >> v;
if (u != -1 || v != -1) {
arr[i].left = u;
arr[i].right = v;
}
}
cin >> k;
for (int i = 1; i <= k; i++)
action(1,i); //루트는 항상 1번 노드이다.
cout << result << endl;
}
이러한 방식입니다. 문제가 많은 코드입니다.
왜냐하면 1 ≤ K ≤ 10^18, 1 ≤ N ≤ 200000 이기 때문에 저렇게 무식한 시뮬레이션으로는 문제를 시간초과가 납니다.
규칙을 찾아야합니다.
위와 같은 문제 규칙에서 2번, 4번, 2번, 5번, 2번 노드에 차례대로 떨어지게 됩니다.
루트노드입장에서 생각해봅시다. k번째를 반복하며 인덱스가 홀수에서는 왼쪽 짝수에서는 오른쪽으로 이동합니다.
3의 입장에서도 보면 인덱스가 홀수에서는 왼쪽 짝수에서는 오른쪽으로 이동합니다.
이러한 규칙이 있기 때문에 굳이 시뮬레이션할 필요가 없습니다.
즉 k번을 반복하는게 아니라, k번째만 확인해 답을 구할 수 있습니다.
정답코드입니다.
#include <iostream>
using namespace std;
struct node {
int left, right;
};
node arr[200001];
int main() {
int n; long long k;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i].left >> arr[i].right;
cin >> k;
int pos = 1; //루트 노드에서 시작
while (1) {
//1
if (arr[pos].left == -1 && arr[pos].right == -1) break;
//2
else if (arr[pos].left == -1) pos = arr[pos].right; //왼쪽노드가 없음 -> 오른쪽으로 이동
else if (arr[pos].right == -1) pos = arr[pos].left; //오른쪽노드가 없음 -> 왼쪽으로 이동
//3
else if (k % 2) {//1)조건 -> 홀수면 왼쪽으로 간다.
pos = arr[pos].left, k = k / 2 + 1;
}
else { //2)조건 -> 짝수면 오른쪽으로 간다.
pos = arr[pos].right, k /= 2;
}
}
cout << pos << endl;
return 0;
}
이중에서 아래 코드를 봅시다.
while (1) {
//1
if (arr[pos].left == -1 && arr[pos].right == -1) break;
//2
else if (arr[pos].left == -1) pos = arr[pos].right; //왼쪽노드가 없음 -> 오른쪽으로 이동
else if (arr[pos].right == -1) pos = arr[pos].left; //오른쪽노드가 없음 -> 왼쪽으로 이동
//3
else if (k % 2) {//1)조건 -> 홀수면 왼쪽으로 간다.
pos = arr[pos].left, k = k / 2 + 1;
}
else { //2)조건 -> 짝수면 오른쪽으로 간다.
pos = arr[pos].right, k /= 2;
}
}
1,2번 조건은 쉽게 이해하실겁니다. 아래 코드에서 k%2와 k/2를 통해서 위치를 판별합니다.
루트기준으로 k번째에서의 떨어지는 방향은 홀수면 왼쪽으로 짝수면 오른쪽으로 이동합니다.
그아래 노드들도 위에서 설명한 규칙대로 이동하기 때문에 k값의 짝,홀수 를 변경해주는 것 입니다.
처음에 가진 생각은 가장 이동경로내에 여러개의 편의점이 있으면 어디를 선택할까와 같은 생각을 했지만, 다시 생각해보니 무의미했습니다. yes, no로 도달할 수 있는지만 판단하면 되었기 때문입니다. 그렇기 때문에 모든 편의점을 탐색하며 도달할 수 있는지 여부만 판단했습니다.
bfs알고리즘을 사용해서 방문여부를 판단했습니다.
주의 하셔야 할 점은 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리) 입니다.
문제를 꼼꼼히 읽는 습관을 가져야 합니다.
아래는 정답코드입니다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
int t = 0, n = 0;
int arr[101][2] = { 0 };
int starting_x, starting_y, destination_x, destination_y;
bool visited[101];
int que[1000000][2] = { 0 };
int started = 0, ended = 0;
void bfs() {
que[ended][0] = starting_y;
que[ended++][1] = starting_x;
while (started != ended) {
int y = que[started][0];
int x = que[started++][1];
for (int i = 0; i <= n; i++) {
if (!visited[i]) {
int len_x = min(abs(x - arr[i][1]), abs(arr[i][1] - x));
int len_y = min(abs(y - arr[i][0]), abs(arr[i][0] - y));
double len_total = len_x + len_y;
if (len_total <= 1000)
{
visited[i] = 1;
que[ended][0] = arr[i][0];
que[ended++][1] = arr[i][1];
}
}
}
}
}
int main() {
cin >> t;
while (t--) {
cin >> n;
cin >> starting_x >> starting_y;
for (int i = 0; i < n; i++)
cin >> arr[i][1] >> arr[i][0];
cin >> arr[n][1] >> arr[n][0];
memset(visited, 0, sizeof(visited));
started = 0, ended = 0;
bfs();
if (visited[n])
cout << "happy" << endl;
else
cout << "sad" << endl;
}
}
#include <iostream>
#include <algorithm>
using namespace std;
int m = 0, n = 0, k =0;
int arr[102][102] = { 0 };
int x, y, x2, y2;
int result[101] = { 0 };
int sum = 0, result_index = 0;
int x_dep[4] = { 1,-1,0,0 };
int y_dep[4] = { 0, 0,-1,1 };
void dfs(int yy, int xx) {
arr[yy][xx] = -1;
sum++;
for (int i = 0; i < 4; i++)
{
int yyy = yy + y_dep[i];
int xxx = xx + x_dep[i];
if (yyy >= 0 && yyy < m && xxx >= 0 && xxx < n) {
if (arr[yyy][xxx] == 0)
dfs(yyy, xxx);
}
}
}
int main() {
cin >> m >> n >> k;
for (int i = 0; i < k; i++) {
cin >> x >> y >> x2 >> y2;
for (int j = y; j < y2; j++) {
for (int u = x; u < x2; u++) {
arr[j][u] = 1;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 0) {
sum = 0;
dfs(i, j);
result[result_index++] = sum;
}
}
}
sort(result, result + result_index);
cout << result_index << endl;
for (int i = 0; i < result_index; i++)
cout << result[i] << " ";
cout << endl;
}
