나이브하게 접근하면 tle 뜬다 변수를 사용하지 않고 같은 로직을 사용해도 런타임에러 뜬다...왜지....
접근방법:
k번째 moo 수열 S(k)은 크게 A, B, C 세 부분으로 구성된다.
S(k-1 ) + (m + o * (k+2)) + S(k-1)
k-1번째 수열이 앞뒤로 있고 중간에 m하나와 o가 k+2개 존재한다.
이 점을 사용하여 n의 값에 따라 적절한 위치로 n을 보내 줄 것이다.
먼저 n길이 이상의 moo 수열이 나오도록 k와 그 때 길이 len을 계산한다.
n의 위치는
n<=tmp면 A부분에,
n>tmp + k + 3이면 C부분에,
나머지 경우엔 B부분에, 라고 할 수 있다.
B부분인 경우 첫 글자만 m이고 나머지는 o이다.
A부분이면 길이를 재조정해준다.
C부분이면 n을 감소시켜 A와 동일하게 만들어준다.
#include <stdio.h>
using namespace std;
long long n;
char result;
int main(void)
{
scanf("%lld", &n);
long long len = 3;
long long k = 0;
while (n > len)
{
k++;
len = len * 2 + k + 3;
}
while (1)
{
long long tmp = (len - k - 3) / 2;
if (n <= tmp)
{
k--;
len = tmp;
}
else if (n > tmp + k + 3)
{
n -= tmp + k + 3;
k--;
len = tmp;
}
else
{
if (n == tmp + 1)
{
result = 'm';
}
else
{
result = 'o';
}
break;
}
}
printf("%c\n", result);
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 1074] Z (0) | 2020.12.13 |
---|---|
[백준 1992] 쿼드트리 (0) | 2020.12.13 |
[백준 1780] 종이의 개수 (0) | 2020.12.12 |
[백준 16505] 별 (0) | 2020.12.12 |
[백준 2167] 2차원 배열의 합 (0) | 2020.12.11 |
댓글