2. Ascending (오름차순 ex: 1 2 3 4) , Descending (내림차순 ex: 4 3 2 1)이 반복되는 형태로 되어있다.
2번 규칙 순서가 바뀌는 것을 제외하고 1번 규칙만을 놓고 나열을 해보면 아래와 같이 숫자가 나열 된다.
1/1
1/2 2/1
1/3 2/2 3/1
1/4 2/3 3/2 4/1
잘 보면
X / 최대 숫자
X + 1 / 최대 숫자 - 1
...
이런식으로 흘러가는 걸 알 수 있다.
이걸 이용해서
X - 최대 숫자 > 0 이면
X = X - 최대숫자, 최대숫자 증가
X - 최대 숫자 <= 0 이면
오름차순 or 내림차순 순서에 따라 X / 최대 숫자 - X + 1 또는 최대 숫자 - X + 1 / X
를 출력해주기만 하면 된다. (이렇게 작성함)
#include <iostream>
using namespace std;
int main()
{
int x;
int num = 1;
bool isAscending = true;
cin >> x;
while (true)
{
isAscending = !isAscending;
if (x - num <= 0)
{
if (isAscending)
{
cout << x << "/" << num - x + 1 << endl;
}
else
{
cout << num - x + 1 << "/" << x << endl;
}
break;
}
x -= num;
num++;
}
}
#include <iostream>
using namespace std;
int GetMin(int a, int b)
{
return a < b ? a : b;
}
int BinarySearch(int n, int k)
{
int left = 1, right = k;
while (left < right)
{
int mid = (left + right) / 2;
int count = 0;
for (int i = 1; i <= n; ++i)
{
count += GetMin(mid / i, n);
}
if (count < k)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return right;
}
int main()
{
int n, k;
cin >> n >> k;
cout << BinarySearch(n, k) << endl;
}
다른 분들이 짠 코드를 봤는데 결국 똑같은 코드가 되어버렸다.
처음에 문제를 봤을 때 이걸 어떻게 이진탐색으로 푸는거지?? 생각이 들었지만 지금은 이해가 되었다.
문제는 이렇다.
2차원 n x n 크기의 배열 A가 있다. (모든 인덱스는 1부터 시작)
각 인덱스에 따라 [i][j] = i x j 의 값이 들어있다.
예를 들어
n = 3이면
[1][1] 1x1 = 1 [1][2] 1x2 = 2 [1][3] 1x3 = 3
[2][1] 2x1 = 2 [2][2] 2x2 = 4 [2][3] 2x3 = 6
[3][1] 3x1 = 3 [3][2] 3x2 = 6 [3][3] 3x3 = 9
이 배열을 B라는 1차원 오름차순 배열로 만든다.
B[1] = 1
B[2] = 2
B[3] = 2
B[4] = 3
B[5] = 3
B[6] = 4
B[7] = 6
B[8] = 6
B[9] = 9
이 중에서 k번째의 값은 무엇인가?
k가 7이라면 B[7] = 6
위의 코드에서 핵심은 count를 세는 방법에 있다.
다시 한번 배열을 살펴보면
[1][1] 1x1 = 1 [1][2] 1x2 = 2 [1][3] 1x3 = 3 i = 1의 배수
[2][1] 2x1 = 2 [2][2] 2x2 = 4 [2][3] 2x3 = 6 i = 2의 배수
#include <stdio.h>
long long BinarySearch(long long start, long long end, long long x, long long y, long long z)
{
long long mid, z2;
long long result = -1LL;
while (start < end)
{
mid = (start + end) / 2LL;
z2 = (y + mid) * 100LL / (x + mid);
if (z2 <= z)
{
start = mid + 1LL;
}
else if (z < z2)
{
end = mid;
result = end;
}
}
return result;
}
int main()
{
long long x, y, z, result;
scanf("%lld %lld", &x, &y);
z = y * 100LL / x;
result = BinarySearch(0, x + 1, x, y, z);
printf("%lld\n", result);
}
이진 탐색을 활용하여 결과를 구할 수 있었다.
퍼센트로 나타내기 위해선 소수점 2자리만 필요하기 때문에 100판 중 40판을 이겼다면
40 * 100 / 100 으로 정수형이기 때문에 소수점을 제외하고 나타낼 수 있다. ( 4000 / 100 = 40 )
이 때 int형은 오버플로우가 발생할 수 있기에 모두 long long 형으로 설정해주었다.
계산 중 실수했던 부분이 게임을 이길수록 전체 판수도 함께 증가해야 된다는 것이었다.
새로운 승률 z2 = (기존 승리 + 추가 승리) * 100 / (전체 판수 + 추가 승리)
BinarySearch 매개변수인 long long end 값은 전체 판수 + 1 (x + 1)로 해주었다.
이 값이 현재 로직에서 탐색의 최대 범위이다.
전체 판수 : 1000000000 (10억) 이긴 판수 : 980000000 (9억 8천)
위의 경우는 총 10억판을 이기면 승률이 98%에서 99%로 올라가게 된다. (1980000000 / 2000000000)
근데 이진 탐색 로직을 보면 z < z2 (기존 승률 < 새로운 승률) 인 경우에만 result를 갱신하게 된다.
end 값이 줄어들어야 result가 갱신이 되는데 end값이 곧 정답이기에 작아질 수가 없기 때문이다.
#include <stdio.h>
#include <stdlib.h> //system("pause") 쓰기 위한 라이브러리
char map[10000][501]; //char 배열은 마지막 null 문자 들어가야되서 크기 + 1
int used[10000][500];
int dirR[3] = { -1, 0, 1 };
int maxRow, maxCol;
int result;
bool finished;
//현재 진행 상태를 볼 수 있게 만든 함수
void PrintState()
{
printf("\n");
for (int i = 0; i < maxRow; ++i)
{
for (int j = 0; j < maxCol; ++j)
{
if (map[i][j] == 'x')
{
printf("x");
continue;
}
printf("%d", used[i][j]);
}
printf("\n");
}
printf("\n");
system("pause"); // 키를 누를 때까지 멈춤
}
void DFS(int row, int col, int num) //Depth First Search
{
//PrintState(); //dfs 탐색 순서를 보고 싶다면 주석 제거
if (col == maxCol - 1)
{
result++;
finished = true;
return;
}
int nextCol = col + 1;
for (int i = 0; !finished && i < 3; ++i)
{
int nextRow = row + dirR[i];
if (0 <= nextRow && nextRow < maxRow &&
map[nextRow][nextCol] == '.' &&
used[nextRow][nextCol] == 0)
{
used[nextRow][nextCol] = num;
DFS(nextRow, nextCol, num);
}
}
}
int main()
{
scanf("%d %d", &maxRow, &maxCol);
for (int i = 0; i < maxRow; ++i)
{
scanf("%s", map[i]);
}
for (int i = 0; i < maxRow; ++i)
{
finished = false;
used[i][0] = i + 1;
DFS(i, 0, i + 1);
}
PrintState(); //탐색 완료 된 형태 출력
printf("%d\n", result);
}
