BBOOR Programming

 문제 링크 F1 :  https://codeforces.com/contest/1560/problem/F1               F2:  https://codeforces.com/contest/1560/problem/F2 문제 F1과 F2의 차이는 k의 범위이기 때문에 F2를 풀면 F1까지 풀린다. 풀이 과정은 다음 과정을 반복한다. 1. n이 k-beautiful 인지 확인하여 맞는다면 n을 출력하고 아니라면 2번 과정을 진행한다. 2. n의 가장 높은 자리부터 순회하면서 숫자의 종류가 k + 1개가 되는 순간의 위치를 확인한다.    해당 숫자가 9가 아니라면 해당 숫자를 +1 하고 4번 과정을 진행한다.    해당 숫자가 9라면 3번 과정을 진행한다. 3. 숫자 9가 아닐 때까지 한자리씩 올라간다. 숫자 9가 아닌 수가 나올 경우 해당 숫자를    +1 하고 4번 과정을 진행한다. 4. +1한 숫자의 위치보다 낮은 자리의 수들을 모두 0으로 정한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #include   < iostream > #include   < set >   using   namespace   std ;   bool  checkBeautiful( string  n,  int  k) {       set < char >  s;   ...

 문제 링크 :  https://codeforces.com/contest/1560/problem/E 문자열 t에서 마지막 문자가 마지막으로 지워진 문자이다. 그리고 마지막에 연속으로 붙어있는 개수가 처음 문자열에 포함되어 있는 마지막으로 지워진 문자의 개수이다. 문자열 t의 마지막 문자부터 처음 문자까지 차례대로 확인하면서 기존에 확인된 문자들 이외의 처음 나오는 문자는 바로 이전에 지워진 문자라는 것을 알 수 있다. 이 과정을 통해서 문자열을 구성하고 있는 문자들과 지워진 문자의 순서를 알 수 있다. 또한 t를 구성하고 있는 각 문자들의 개수를 세어 처음 문자열에 포함되어 있는 각 문자의 개수를 알 수 있다. 지워진 문자의 순서를 안다면 각 문자마다 문자열 t에 몇 번 붙여졌는지 횟수를 알 수 있고 이 횟수로 문자열 t에 포함된 문자의 개수를 나누면 초기 문자열에 포함된 각 문자의 개수를 알 수 있다. ( 이때 각 문자마다 이 나누기 계산을 진행했을 때 나머지가 0이 아니라면 -1을 출력한다. ) 그리고 이 정보를 이용해 초기 문자열의 길이를 알 수 있고 해당 길이만큼 문자열 t에서 확인했을 때 이전에 계산했던 각 문자의 초기 문자열에 있는 개수와 전부 맞는다면 문자열 t에서의 초기 문자열이 될 수 있다는 의미이고, 개수가 맞지 않다면 -1을 출력한다. 초기 문자열까지 구했다면, 이 초기 문자열과 이전에 구했던 지워진 순서를 이용하여 문자열 t를 만드는 과정을 그대로 진행하여 입력받은 문자열 t와 일치한다면 답을 출력하고 일치하지 않는다면 -1을 출력한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 ...

 문제 링크 :  https://codeforces.com/contest/1560/problem/D 숫자 n의 최댓값은 10억이다. 따라서 10자리의 숫자는 10억 한 개, 나머지 중 가장 높은 자릿수를 가지는 숫자는 최대 9자리 숫자이다. 9자리 숫자가 최대한 높은 자리의 2^k인 수를 만드는 경우는 9자리에 계속 숫자를 붙이는 경우다. 9자리 숫자에서 최대 움직임 수는 9자리 숫자 모두 지운 후 하나의 수를 붙여 총 10번 움직이는 것이다. 9자리 숫자가 아무리 많이 움직여야 하는 숫자라도 최대 10번이라는 것이다. 그러므로 만약 9자리 숫자에 숫자를 10번 붙이거나 9자리 숫자를 다 지우고 하나 붙여서 10번 작업하는 것 두 가지의 경우 아무거나 상관없으므로 9자리 수에 최대한 많이 붙여지는 경우의 2^k의 자릿수는 18자리가 최대이다. 2^k인 수 중 18자리인 수들까지의 숫자의 개수는 총 59개이다. 그렇기 때문에 이 59개의 수들을 모두 구해놓고 숫자 n과 59개의 수를 비교하여 가장 적은 횟수로 만들어지는 경우를 찾는다. 각 숫자와 비교하여 만들어지는 횟수를 찾는 방법은 다음과 같다. 2^k인 수를 x라 하자. x의 가장 높은 자리의 숫자부터 차례대로 n에 존재하는지 확인한다. n을 탐색할 때 가장 높은 자리부터 탐색해 나간다. 존재한다면 x의 바로 다음 자리의 숫자를 탐색하고 이 방식대로 x의 모든 숫자를 탐색한다. 탐색하다가  n의 모든 숫자의 순회가 끝나게 되면 이 과정은 끝나게 된다. 이때 x의 모든 숫자가 n에 포함되어 있지 않을 수 있고 가장 높은 자리의 숫자부터 임의의 개수의 숫자가 포함되어 있을 것이다. 모든 탐색이 끝났을 때 n에서 x를 구성하는 숫자와 순서에 맞게 일치하는 숫자의 개수를 알 수 있다. 이 개수를 num이라고 할 때, n을 구성하고 있는 숫자의 개수 - num 개수가 지워야 하는 숫자의 개수이고 x를 구성하고 있는 숫자의 개수 - num 개수가 붙여야 하는 숫자의 개수이다. 그러므로 n에서 ...

 문제 링크 :  https://codeforces.com/contest/1560/problem/C 채워지는 수들 중 가장 윗줄의 수가 채워지는 규칙을 보면, 1  2 (+1)  5 (+3)  10 (+5) ~~ 이런 식이다. 더해지는 수를 d라고 한다면 더해지는 수 d가 한번 더해질 때마다 +2씩 늘어난다. 이 윗줄의 수를 계산해서 a <= k < a + d인 a를 찾는다. 1   2   5   10   ~~   a   a+d 이런 구성이다. 여기서 a의 r = 1, c = ( a까지 채워진 숫자의 개수 ) 가 된다. 숫자가 채워지는 규칙이 윗줄의 수부터 행렬을 둘러싸는 규칙이기 때문에 a의 r, c를 아는 상태로 k에 대해서 r, c의 값을 찾는 규칙은 아래와 같다. if ( k <= a + d/2 ) -> r = 1 + (k - a), c = c else if ( k > a + d/2 ) -> r = 1 + d/2, c = c - ( k - ( a + d/2 ) ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include   < iostream >   using   namespace   std ;   int  main() {        int  t;      cin   > >  t;        while  (t - - ) {         ...

 문제 링크 :  https://codeforces.com/contest/1560/problem/B a와 b는 마주 보고 있다. a < b라고 하자. ( a가 더 크다면 값을 바꾼다. ) a와 b가 마주 보고 있을 수 있도록 원을 구성하기 위해서는 a ~ b, b ~ a 2가지 범위에 숫자의 개수는 b - a - 1개 여야 한다. 그렇다면 일단 첫 번째 범위에는 무조건 a, ( b - a - 1개의 숫자 ), b로 구성되어 있다. 그리고 두 번째 번위는 b ~ a인데, 여기서 생각해야 할 점은 a가 어떤 수냐에 따라 1 ~ a - 1까지의 숫자가 이 범위에 포함되고 나머지 자리에 b보다 큰 숫자들이 차례대로 구성되어 있어야 한다는 것이다. 그렇다면 원이 구성되기 위해서는 1 ~ a - 1까지의 숫자 개수가 b - a - 1개의 숫자보다 크지 않아야 한다. b - a - 1개라면 1 ~ a - 1까지의 수로 구성되어 있는 것이고, b - a - 1개보다 작다면 1 ~ a - 1, 나머지 개수는 b+1, b+2, ~~로 구성되어 있는 것이다. 여기까지 확인했으면 일단 입력된 a와 b로 올바른 원을 구성할 수 있다는 의미다. ( 예를 들어 a = 2, b = 3 이라면 숫자로 원을 그려봤을 때 a와 b가 마주 보고 있는 원이 안 그려진다. ) 올바른 원이 그려졌다면 이제 c가 원의 범위에 들어가는지 확인한다. c가 범위에 들어간다면, if ( c <= 원을 구성하는 가장 큰 수 ) -> c + (b - a) else if ( c > 원을 구성하는 가장 큰 수 ) -> (c + (b - a)) % 원을 구성하는 가장 큰수 가 답이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include   < iostream >   using ...

 문제 링크 :  https://codeforces.com/contest/1560/problem/A k가 최대 1000이기 때문에 먼저 1000번째 숫자까지 구한 후 case마다 답을 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include   < iostream >   using   namespace   std ;   int  main() {        int  v[ 1001 ];     v[ 1000 ]  =   0 ;        int  idx  =   1 ;      int  num  =   1 ;        while  (v[ 1000 ]  = =   0 ) {            if  (num %  3   ! =   0   & &  num %  10   ! =   3 ) {             v[idx]  =  num;             idx + + ;  ...