The Way

*.. .*. *.. 와 같은 식으로 n * n 크기의 board가 주어질 때, manhattan distance를 기준으로 정삼각형을 이루는 세 쌍의 *의 수를 구하는 문제이다. 모든 쌍을 다 해보려면 시간 복잡도는 $O(n^6)$이고, 점을 두 개만 고르면 나머지 한 점의 가능한 위치는 정해지므로 이 방법을 사용한다 해도 시간 복잡도는 $O(n^4)$이다. n = 300이므로, 조금 더 나은 방법을 찾을 필요가 있다. 먼저 적절한 관찰을 통해 정삼각형이 가지는 특징을 알아낼 필요가 있다. 한 변의 길이가 d인 정삼각형은 적절한 90도 단위의 회전을 통해, 좌표가 $(p, q), (p + x, q + (d - x)), (p + y, q + (d - y))$ $(0 \le x \le d, 0 \le y ..

문제는 아주 심플하다. N * M짜리 배열에서, 1≤i

매일 저녁 6시경에 하루 3백준(≥플레 1문제, 골드 1문제, ≤실버 1문제)을 랜덤으로 뽑아서 풀고 있는데, 보통 플레 이상은 풀 확률이 반반 정도 되는 편. 그 중 간만에 재미있는 문제 하나를 발견해서 기록을 남겨본다. 초기 0, 1, 2가 들어있는 집합이 있고 이 집합의 원소 중 x, y 둘을 골라(같아도 됨) $x^2 - y$를 집합에 추가해주는 operation을 가해줄 수 있다. 최대 43번의 operation을 가해서 $10^{18}$까지의 숫자를 만드는 것이 문제의 목표이다. 정답은 뭐 크게 어렵지 않고, p를 만들려면 $x^2 \ge p$를 만족하는 가장 작은 x를 찾고, y는 $x^2 - p$를 사용하면 된다. 이후 x, y 만들기를 목표로 이 과정을 반복하면 된다. p의 크기는 최대 ..

드디어 백준에도 인터랙티브 문제들이 생겼다. Codeforces에 이따금 출현하는 인터랙티브와는 사뭇 다른 느낌인데, 코포에서는 입출력을 통해 통신(?)을 한다면 백준은 함수 호출을 통한 인터랙티브를 사용한다. 삼성 B형에도 이따금 출제되는 유형이기도 하니, 코딩테스트를 목표로 하는 사람이라면 한번쯤 풀어보아도 좋을 듯 하다. 뒹굴면서 페북을 보다가, 인터랙티브 테스트 대회라고 있길래 후다닥 해보았다. 비공식 대회지만 처음으로 1등했다.. ㅋㅋ 내가 잘했다기보다는 잘하는 사람들이 크게 관심을 안가진 덕이 크다. 백준 18158. What an Easy Problem 생략. 문제를 잘 읽읍시다. 18158.cpp 백준 18159번. Have You Ever Sorted an Array? 1~n으로 구성된 ..

잠이 잘 안와서 가볍게 쓰는 글. 유니콘의 이동 경로대로 문자열을 만들 때 가능한 경우의 수를 구하는 문제. 유니콘은 나이트랑 비슷하게 움직이는데, 나이트는 (2칸, 1칸)을 움직이는 대신 유니콘은 (3칸 이상, 2칸 이상)을 움직여야 한다. 유니콘이 이동할 수 있는 곳들을 보드판에 나타내보면 다음과 같다. 상당히 예쁜 모양. 같은 맥락에서, 색칠된 위치에 유니콘이 있었다면 다음 턴에 Uni의 위치로 이동가능하다는 말도 된다. 결국 맨 처음에 문자열의 0번 위치와 같은 문자들이 놓인 보드판에 경우의 수 1씩을 할당하고, 그 다음부터는 문자열과 같은 문자가 쓰여진 보드판에 저 위치의 경우의 수의 합을 차례로 할당하면 된다. 보드판 크기가 300이고 L은 26이므로 복잡도는 단순 구현시 $300^4 \tim..

주어진 종이를 여러 번 적당히 잘 접어서 만들 수 있는 가장 큰 수를 찾는 문제이다. 접어서 같은 위치에 겹치게 되는 숫자는 합해주면 된다. N과 M이 12 이하이므로, 완전 탐색 문제라는 것은 어렵지 않게 알 수 있다. 다만 완전 탐색 치고 생각보다 까다롭다. 가로를 접는 경우의 수와 세로를 접는 경우의 수는 순서로 따지면 각각 넉넉잡아 11!개 정도이고, (실제로는 7만 4000개 정도이다), 겹쳐진 상태만 고려한다고 해도 $2^{12}$ 가지이다. 둘을 곱해주면 $2^{24}$ 정도로 시간초과나기 딱 좋은 수치이다. 약간 관찰을 해 보면 겹쳐진 상태가 $2^{12}$가지 보다는 훨씬 더 적다는 것을 알 수 있다. 예컨대 길이 4개짜리를 접어서, 1, 3, 4번만 겹치도록 만드는 것은 불가능하다. 그..

팀의 수 n과 n개의 팀 각각의 승리 횟수가 주어졌을 때, 유효한 횟수인지 아닌지 찾는 문제.2016 대전 ACM-ICPC 본선에 나온 문제이다. 예를 들어 n이 4이면,0 2 1 3과 같은 승리 횟수는 가능하지만0 3 3 0과 같은 승리 횟수는 불가능하다. 한 팀이 3회 이기면, 다른 팀은 무조건 패가 하나는 생기기 때문에 3이 또 올 수 없기 때문이다. 이 문제는 사실 잘 알려진 문제이다.모든 팀이 서로 다른 팀들과 경기를 할 때 생기는 그래프를 Tournament 그래프라고 한다.tournament 그래프의 score sequence가 유효한지를 알아내는 정리로 Landau's Theorem이라는 것이 있다. score sequence를 non-decreasing하게 재배치한 뒤(=정렬), 각각을 ..

조세퍼스 문제 시리즈를 풀어보았다. 조세퍼스 문제는 꽤 유명한 문제인데, 사람 n명이 원탁에 순서대로 둥글게 둘러앉은 뒤, 처음에 k번째 사람이 집에 가고, 그 다음에 집에 간 사람의 위치를 기준으로 하여 k번째 사람을 제거하고.. 를 반복하는 문제이다. 7명일 때 k가 3이면 다음과 같다. 1 2 3 4 5 6 7 => 3 1 2 4 5 6 7 => 6 1 2 4 5 7 => 2 1 4 5 7 => 7 1 4 5=> 5 1 4 => 1 4 => 4 백준 1158번: 조세퍼스 문제 정직한 구현 문제. 보통 큐를 이용하는데, 처음에 숫자를 순서대로 넣고 k - 1번 큐에서 빼고 집어넣은 뒤, 마지막 k번째 사람은 집어넣지 않고 출력한다. 대략 큐를 처음 써보는 사람들을 위한 문제 정도다. 백준 1168번:..

자연수 n이 주어질 때, n을 서로 다른 피보나치 수의 합으로 나타내는 문제이다. 이 때 사용하는 피보나치 수의 갯수는 최소가 되어야 한다. 풀이는 생각보다 간단하다. n보다 같거나 작은 피보나치 수 중 가장 큰 피보나치 수를 사용하고, 이를 반복하면 된다. 가령 n=100이면 89를 사용하고, 남은 11에 대해서 8을 사용하고, 또 남은 3에 대해 3을 사용하면 된다. 답을 때려맞추기는 상당히 쉬운 문제이지만, 왜 그게 성립하는지 증명하기는 상당히 까다롭다. 과연 이 방법이 왜 최적의 해를 가져올까? 예시와 함께 증명을 해보자. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 89~143까지의 숫자에 대해 생각을 해보자. i) 임의의 수에 대해, n보다 같거나 작은 피보나..

자기 전에 한 문제만 풀고 자려고 했는데, 이 문제 때문에 잠을 못잤다. 케이스가 상당히 극악인 문제이다. 문제는 아주 심플하다. 방정식 Ax + By + C = 0의 정수해의 개수 구하기이다. x와 y는 x1 ≤ x ≤ x2, y1 ≤ y ≤ y2를 만족해야 한다. 각 수의 범위는 -10^8 ~ 10^8이다. 일단 수의 범위가 상당히 크기 때문에 직접 다 해보는 알고리즘은 시간초과가 뜰 가능성이 농후하다. 케이스를 나누어가며 접근해보자. i) A와 B 둘 다 0인 경우 가장 쉬운 경우이다. C = 0이면 모든 해가 정답이고, C ≠ 0이면 해가 없다. ii) A와 B 둘 중 하나만 0인 경우 편의상 A = 0, B ≠ 0이라 해보자. 그럴 경우 방정식은 By + C = 0이 된다. C가 B로 나누어 떨..