Codeforces Round #479(Div. 3)

C. Less or Equal

쉽게 풀 수 있을 것이라고 생각했는데, 틀려서 고민 좀 했다.
틀린 이유는 입력 조건을 제대로 확인하지 않아서 였다. (0 <= k <= n) 라는 입력 조건때문에 k값으로 0이 들어올 수도 있다.
k값이 0인 경우를 처리해주지 않아서 틀렸고, 이를 처리하여 AC를 받았다.

D. Divid by three, multiply by two

입력으로 수열이 주어지면 이전 수에 3으로 나누거나(3으로 나누어 떨어질 때 가능), 2를 곱하는 연산 둘 중의 하나를 시행하여 다음 수가 나오도록 수열을 재배치 하는데, 정답이 있다는 것이 보장된다.
나는 각 수에서 시작해보는 백트래킹 같이 재귀를 이용해 풀었는데, 같이 푼 친구는 각 수에서 시작하여 그래프를 만들어 보는 식으로(*2, /3 연산 중에 다음 수가 그 배열에 존재하는 경우에만 그래프를 만든다) 했는데, 신기하게도 그렇게 하면 한줄의 그래프가 만들어지는 것 같다. 그렇다면 애초에 어떤 수 x가 있을 때, 2x와 x/3이 둘 다 그 수열에 존재하면, 답이 나올 수 없는건가?
생각해보니 그렇다. 좀 더 정확히 말하면 어떤 수 x가 있을 때 2x를 다음 수로 하면 x/3은 그 이후에 절대 나올 수 없고, 마찬가지로 x/3을 다음수로 하면 2x는 그 이후에 절대 나올 수 없다.
1) x -> 2x가 된 경우
일단 x/3이 가능하려면 x는 3을 인수로 갖는다. 그런데 2x가 되면 인수 2가 추가 되고, x/3이 나오려면 추가된 인수 2를 없애야 하는데, 크기를 줄이는 방법은 /3밖에 없으므로 결코 x/3이 될 수 없다.(결코 x/3과 같은 인수를 가진 수가 나올 수 없다.)
2) x -> x/3이 된 경우
x는 3을 인수로 가지고 있는데 x/3은 2x에 비해 인수 3이 하나 적어지게 된다. 그런데 크기를 늘리는 방법은 *2밖에 없으므로 결코 2x가 나올 수 없다.(2x와 같은 인수를 가진 수가 나올 수 없다.)

그리고 마지막으로 출제자의 공식 풀이를 봤는데...

수열의 각 수의 인수 3의 개수를 세서 인수 3의 개수가 많은 순(내림차순)으로, 인수 3의 개수가 같으면 수의 크기가 작은 순(오름차순)으로 정렬한 후에, 그대로 수를 출력해주면 답이 된다....

엄청 간단하다... 과연 저렇게 해도 되는걸까?
생각해보면, 답이 존재한다는 게 보장되므로, 일단 3을 인수로 가지는 수가 있을 때, 우리가 할 수 있는 연산은 *2, /3뿐이므로 그 수를 만들기 위해서는 먼저 3을 인수로 가지는 수가 필요하다. 만약 인수 3의 개수가 같은 경우는 작은 쪽에 *2를 해서 만들 수 있을 것이고 개수가 다른 경우는 큰 쪽에 /3을 해서 작은 쪽을 만들 수 있을 것이다.

즉, 인수 3의 개수가 다르면 *2를 사용할 수 없고(*2를 쓰려면 인수 3의 개수가 같은 수가 존재해야 한다) /3만 가능하므로 내림차순으로 정렬하고, 인수 3의 개수가 같은 경우는 *2밖에 안되므로 오름차순으로 정렬해주면 된다.


E. Cyclic Components

일반적인 사이클이 아닌 문제 조건에 맞는 사이클을 찾는 문제인데 일반 사이클 문제보다 아주 약간 더 까다로웠다. 방문하지 않은 점부터 dfs를 해서 시작 점과 직전 점을 같이 parameter로 보내서 직전 점으로는 가지 않고, 결국 시작 점으로 돌아오면 사이클인 것으로 판단했고, 중간에 한 정점에 연결된 간선이 2개가 아니면 커트했다. 이 문제에서의 사이클은 한 정점에 간선이 2개만 연결되어 있어야 한다.

근데 이 문제 역시 공식 풀이를 보니...
일반적인 dfs를 사용하면서 vector에 한 번 dfs할 때마다 방문한 정점을 모아놓고, 그 정점들이 모두 각각 간선을 2개씩 가지고 있는지 체크해서 모두 간선을 2개씩 가지고 있으면 사이클로 본다. 하나의 정점이라도 간선이 2개가 아니라면 문제에서 요구하는 사이클이 아닐텐데, 한 번에 방문할 수 있는 모든 정점이 간선을 2개씩 가지면 문제에서 요구하는 사이클일까?  직접 그려보고 해보니 정말 dfs로 한 번에 방문 가능하면서 간선이 2개이려면 그럴 수 밖에 없다... 공부 좀 더 해서 증명도 해봐야겠다.


F. Consecutive Subsequence

이 문제는 가장 긴 증가 부분 수열 문제와 비슷해 보이는데, 1씩 증가하는 부분 수열이어야 한다. 그래서 dp로 풀 경우 일반적인 가장 긴 증가 부분 수열은 O(n^2)이 걸리는 반면에, 이 문제는 dp로 O(n)만에 풀 수 있다.
d[n] = n을 마지막으로 하는 가장 긴 1씩 증가하는 부분 수열의 길이
d[n] = d[n - 1] + 1이 된다.

일반적인 가장 긴 증가 부분 수열은 n보다 작은 모든 값에 대해 살펴봐야 해서 O(n^2)이지만, 1씩 증가하는 경우는 n - 1에 대해서만 보면되니까 O(n)이다.

물론 가장 긴 증가 부분 수열의 경우 O(nlogn)에 푸는 풀이가 있긴한데, 그 풀이도 공부해 봐야겠다.

그리고 이 문제에서는 수가 매우 커서 map(혹은 좌표압축)을 이용해 dp배열을 구현해야 한다.

백준 14891 톱니바퀴

톱니바퀴는 0번부터 3번까지 4개가 일렬로 있고, 0 - 1 - 2 - 3 이렇게 맞닿아(-) 있다.
한 톱니바퀴 당 톱니가 0번에서 7번까지 8개가 있는데, 맞닿아 있는 톱니는 2번과 6번이다.

0번이 돌아가면 1번이 돌아간다.
1번이 돌아가면 0번과 2번이 돌아간다.
2번이 돌아가면 1번과 3번이 돌아간다.
3번이 돌아가면 2번이 돌아간다.

어떤 톱니바퀴가 돌면, 자신의 양 옆 톱니바퀴가 영향을 받아 돌아가게 하되,
회전 횟수 한 번 당, check 배열을 사용해서 한 번 돈 것은 돌지 않는 식으로 처리하면 될 것 같다.

그리고 돌리기 전 2번, 6번 톱니를 비교해서 옆의 톱니바퀴에 영향을 줄지 말지를 결정해야 한다.

영향을 주는 것이 결정되면 배열에 들어가 있는 값을 이동시켜 돌려주면 될 것 같다.

백준 1475 방 번호

내 풀이의 핵심을 설명하자면,

9를 6대신 쓸 수 있고, 6을 9 대신 쓸 수 있으므로 6과 9를 같은 숫자로 보는 것이다.

같은 숫자로 보면 한 세트에 2개씩 있으므로 (6의 개수 + 9의 개수) / 2 개만큼 필요할 것이다. 이렇게 해서 다른 숫자들의 개수와 비교를 해서 최대값을 구하면 그 값이 필요한 세트의 개수의 최소값이 된다.

*** 그런데, (6의 개수 + 9의 개수) / 2 할 때, 정수 나눗셈이기 때문에 정확히는 (6의 개수 + 9의 개수 + 1) / 2 개 만큼 필요할 것이다.

그리고 나는 숫자로 입력받아서 10으로 나누면서 한 자리씩 취하는 방법을 이용했는데, 이 경우 0이 입력으로 들어오면 count를 하지 못하므로 ans = 1로 초기화 해두는 방법을 이용했다.

백준 15897 (UCPC 2018 예선 H번) 잘못 구현한 에라토스테네스의 체

이 문제는 UCPC 때는 3시간 내내 붙잡고 있다가 못 푼 문제인데... 결국 풀었다.
내가 푼 방법을 정리해 보고자 한다.

----------------------------------------------
1  int n;
2  cin >> n;
3  int* sieve = new int[n + 1];
4  for(int i = 1; i <= n; i++) {
5      for(int j = 1; j <= n; j += i) {
6          sieve[j] += 1;
7      }
8  }

----------------------------------------------

주어진 코드에서 6번째 줄이 입력으로 들어오는 n에 따라 몇 번 실행되는지를 구해야 하는 문제인데, 예를 들어 n이 4라고 하면
j = 1, 2, 3, 4
j = 1, 3
j = 1, 4
j = 4
이렇게 총 9번 실행된다.

바깥쪽 for문의 i 값에 따라 안쪽 for문의 실행횟수가 결정된다고 볼 수 있다.
안쪽 for문에서 j = 1부터 시작하여 i만큼 더하면 n이하일 때까지 반복하므로,
각 i마다 (n - 1) / i 만큼 안쪽 for문이 실행된다.

근데 n이 최대 10억까지 입력으로 들어오기 때문에... 일일이 다 더했다간 시간초과이다.
여러 방법을 고민해보다가 n / 2, n / 4정도까지 줄이기도 해봤었는데... 역시나 1초에 들어오기는 버겁다.

하지만 잘 생각해보면 O(루트n)만큼으로 줄일 수 있다.
내가 찾은 방법을 설명하기가 쉽지 않아서, 예를 들어서 설명해 보겠다.

n이 12인 경우를 예로 들어보면,
j = 1부터 시작하고, n번 모두 1부터 시작하므로 n번 도는 것은 무조건 확정이고,
거기에 (n - 1)을 i로 나눈 몫을 구해서 더해야 한다. 그런데, 모든 i에 대해 그 몫을 구할 필요가 없다.
숫자(a) 자신과 1만 약수로 갖는 소수를 구할 때에도 보면, 2부터 (a - 1)까지 다 나눠보고 나누어 떨어지는지(1과 자기 자신 외의 약수가 있는지)를 알아보는 방법도 있지만, 굳이 다 나누어 볼 필요 없이 (루트a) 까지만 나누어 보면된다.
12를 예로 들면
2 * 6 = 12
3 * 4 = 12
4 * 3 = 12
6 * 2 = 12
에서 볼 수 있듯이, 2, 3까지만 나누어 보면 4, 6으로 다 나누어 본 것과 같으므로...
(루트a)이하의 수로 나누면 (루트a)이상의 수로 나눠본 것과 같다는 것을 알 수 있다.

마찬가지로 이 문제에서도 똑같이는 아니지만 비슷한 개념을 적용해 볼 수 있다.
n = 12라고 하면, 먼저 1부터 시작하므로 변수 ans(답)에 12를 저장해둔다.
그리고 (n - 1)인 11을 1부터 11까지 나눈 몫을 다 더해주면 답이 되는데,

1 * 11
2 * 5
3 * 3
4 * 2
5 * 2
6 * 1
7 * 1
8 * 1
9 * 1
10 * 1
11 * 1

가 된다. 그래서 12 + 11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 41 이 답이다.

잘 보면 1 * 11 과 11 * 1, 2 * 5와 5 * 2, 가 짝을 이루고 있는 것을 볼 수 있는데,
x * x <= 11인 x = 3까지만 보면, 즉 1 * 11과 2 * 5를 보면 11 * 1과 5 * 2까지 해보지 않고
알 수 있다.

하지만, 좀 부족하다. 3 * 3은 당연히 짝이 없다해도, 4 * 2, 6 * 1, 7 * 1, ... 10 * 1 은 어떻게 예상할 수 있을까?
(루트n)까지 하는 것으로는 부족한 것이 아닐까? 다 해봐야 하지 않을까?

2 * 5로 5 * 2를 알 수 있다. 그런데  4 * 2를 알 수 있는 2 * 4는 왜 없을까? 4 * 2는 되는데 왜 2 * 4는 되지 않을까?

11 = 4 * 2 + 3 이지만 11 = 2 * 5 + 1이다. 즉 나누는 수가 2이냐 4이냐의 차이이다.
2로 나누면 나머지가 2보다 작아야 하기 때문에 몫이 크게 나온다. 4로 나누면 나머지가 4보다 작으면 되니까 몫이 2까지 나온다.

그럼 3 * 2는 어떨까? 3 * 2 + 5 = 11인데, 나머지 5가 3보다 크기 때문에 안된다.
4 * 2 + 3 = 11로 나머지 3이 4보다 작아서 가능한 것과 차이가 있다.

즉 2 * 5를 보면 5 * 2가 된다는 것은 바로 알 수 있지만, 4 * 2가 되는지, 3 * 2가 되는지는 판단하는 작업이 필요하다. 물론 이것을 일일이 확인하면 시간복잡도가 커진다.
위에서 보았듯이, x * 2가 가능하려면, n - x * 2 < x 가 되어야 한다.

여기서는 2이지만 이를 모든 경우에 적용하면
n - x * i < x 이어야 하고, 이를 정리하면, x > n / (i + 1) 이다.
즉, x * i가 가능한 x값의 하한값은 (n + i + 1) / (i + 1)이 되는 것이다.

lo = (n + i + 1) / (i + 1) 이라고 하면
lo값부터 (n - 1) / i 값까지 모두

lo * i
(lo + 1) * i
.
.
.
((n - 1) / i) * i

라는 것을 유추할 수 있는 것이니, ans += ((n - 1) / i - lo + 1) * i 를 해주면 된다.

단, 주의해야할 것은 3 * 3 같이 제곱 수들은 여러번 더해지면 안되는데, 한 번 더 더해진다.
그래서 (n - 1) / i 와 i값이 같을 때는 i만큼 빼줘야 한다.

자료형도 long long으로 하였고, 결국 이렇게 해서 AC를 받았다.

백준 10803 정사각형 만들기

엄청 어려워 보였는데, 생각해보니 간단할 것 같기도 하다.

문제 조건을 보면 한 번 짜르면 무조건 끝까지 잘라야 하고, 수평/ 수직으로만 자를 수 있기 때문에...

d[n][m] = n * m의 직사각형을 잘라서 얻을 수 있는 정사각형 조각의 최소 개수

로 놓고, 수평으로 자르는 경우, 수직으로 자르는 경우 1 ~ n, 1 ~ m 모든 경우를 다 보면서 그 중 최소값을 얻어내면 될 것 같고,

최소값을 구해야 하므로 n == m인 경우 더 자를 필요 없이 1을 리턴해주는 식으로 구현하면 될 것 같다. 

그런데, 생각해보니 그렇게 하면 시간 복잡도가 n * m * (n + m)이 될 것 같은데...

100억 정도가 되어 너무 크다. 그런데 생각해보면 n + m부분에서 n + m을 다 해볼 필요 없이, 그러니까 1 ~ n, 1 ~ m을 다 볼 필요 없이 절반까지만 보면 될 것 같다. 어차피 절반 이후로는 똑같으니까... 

음... 그래도 여전히 시간복잡도가 크다. 그런데 위와 같이 절반까지만 보기 때문에 재귀로 구현하면 d[n][m]에 해당하는 n * m부분이 정말 n * m만큼 호출될 것 같지는 않다.... 일단 구현해 봐야겠다.

제출했더니 역시나 시간초과가 떴다...

어떻게 줄여야할까?

음 일단 생각나는 것이... d[w][h] 나 d[h][w]나 같다는 것이다. 이것을 한 번 적용해 봐야겠다.  그러면 또 반 정도 줄일 수 있을 거 같긴하다.

음 그런데, 저것을 적용하니 좀 답이 잘못 나온다.(10000, 100인 경우에...)

왜 그런지 이유는 잘 모르겠지만... -> 생각해보니 애초에 dp배열크기가 d[10001][101]이라 그런 것 같다. w와 h의 범위가 다르다... 그래서 배열 범위를 초과하여 잘못된 값이 들어간 것 같다.

일단 또 생각해본 것이 w나 h 둘 중 하나가 1인 경우 굳이 더 나눠 볼 필요가 없다는 것이다. 일단 이 부분을 추가해도 시간이 그리 단축되지는 않는다.

확실하지는 않은데, w와 h의 gcd(최대공약수)값부터 자르거나 최대공약수 단위로 자르는 건 어떨까? 최대공약수가 1이면 1부터 해야겠지만, 최대공약수가 2이기만 해도 엄청 많이 줄일 수 있을 것 같은데...

확실하게 증명은 할 수 없지만... 일단 최대공약수부터 시작해서 최대공약수 단위로 자르는 식으로 구현해 봐야겠다.

일단 예제에 대해서는 제대로 나오기는 하는데, 시간초과를 받았다... 9999 100 같은 케이스에 대해서는 여전히 느리다.

백준 15685 드래곤 커브

일단 규칙을 좀 생각해봤다.

1. k세대는 (k - 1)세대를 시계방향으로 90도 돌린 후에 (k - 1)세대의 끝점에 90도 돌린 것의 끝점을 붙이게 된다. 그래서 (k - 1)세대의 역방향으로 새로운 길이 추가된다고 볼 수 있다.
역방향은 x, y방향은 각각 유지하면서 부호만 바꿔주면 된다.

2. 그리고 시계방향으로 90도 돌릴 경우 각 이동 규칙은...
y방향 음수 -> x방향 양수
y방향 양수 -> x방향 음수

x방향 음수 -> y방향 음수
x방향 양수 -> y방향 양수

일단 x -> y, y -> x 가 되고, y방향의 경우만 부호가 바뀐다.
(x, y) -> (-y, x) 로 해주면 된다.

규칙 1과 2를 이용해서 점을 찍고나서
모든 점을 돌면서 각 점마다 오른쪽, 아래 방향으로 1 * 1 정사각형을 구성하는 꼭지점이 있는지 확인해 보면서 1 * 1 정사각형의 개수를 세면될 것 같다.

규칙 1과 2를 이용해서 점을 찍는 부분의 구현이 좀 까다롭다.
먼저 k세대를 구하기 위해서 0세대부터 시작을 한다.
i세대의 이동 방향을 reverse해주고, 그 값을 90도 돌려주는 작업을 해준다.
그리고 i세대의 끝에 이어 붙인다. 그러면 (i+1)세대의 이동방향이 완성된다. 각 이동 방향은 pair(x, y)로 묶어서 vector에 이어붙일 것이다.

이렇게 k세대의 이동방향을 구하면 그를 토대로 점을 check해준다.

결국 이렇게 구현해서 AC를 받았다.
코드가 꽤 길어졌는데, 맞은 사람을 보니 짧게 구현한 사람도 꽤 있다. 이해는 잘 안 가지만, 좀 더 간단히 구현할 수 있는 방법이 있는 것 같다... 더 열심히 해야겠다.

백준 1005 ACM Craft

먼저 주어진 건설 순서를 이용해서 그래프를 만들고, 지어야 할 건물 W부터 시작해서 거꾸로 탐색하는 방식으로 dp로 구현해 볼 생각이다.

거꾸로 탐색하면서 건물 W를 짓기 전에 지어야 할 각 건물까지의 시간 중 최대값을 선택하는 방식으로 하면 될 것 같다. 그리고 이미 탐색한 부분은 메모이제이션을 통해 더 탐색하지 않도록 한다.

위상정렬 문제를 예전에 푼 것을 좀 찾아봐서 다시 풀어봐야겠다.
이 문제는 그냥 그래프 + dp처럼 풀어서 AC를 받았는데, 예전에 풀었던 문제 중에 경로까지 출력해야 하는 문제가 있어서 좀 까다로웠던 것 같고 위상정렬을 풀기 위한 방식이 있었는데... 기억이 잘 안난다. 찾아서 풀어보자!