enopid 님의 블로그

https://www.acmicpc.net/problem/15328문제 분석 3차원에서 원점부터 4개의 지점을 순차적으로 방문할 때 총 이동거리가 X보다 큰지 작은 지를 묻는 문제이다.단순히 각 지점간 거리를 더해서 X와 대소 비교를 하면 되어 보이지만 문제가 long double보다 더 높은 정밀도를 써야 하여 16바이트 자료형인 __float128을 사용해야 하고 그에 따라 거리를 구하기위해 필요한 sqrt함수도 직접 구현해야 한다.  $($파이썬의 경우 decimal 자료형을 사용하면 자료형 자체에서 sqrt를 지원하여 쉽게 구현가능$)$문제 해결 전략 __float128을 사용하고  sqrt 함수를 구현하는 것이 문제의 전부이다. 제곱근은 바빌로니아 방식을 사용하거나 뉴턴 랩슨방식을 통해 구하면 ..

https://www.acmicpc.net/problem/17234문제 분석 문제는 0점부터 시작하여 3가지 선택을 반복하며, $($1. 점수에 a점 추가  2. 점수에 b점 추가 3. 점수를 2배$)$두 가지 조건을 만족시키며 $($1. 점수가 N+a 미만 2. 2배 한 횟수가 전체의 10% 이하$)$가장 빨리 N에 도달하는 문제이다. 기본적으로 점수, 턴 수, 2배 횟수 총 3가지를 고려해야 하므로 시간복잡도 $N^3$의 DP 문제로 하면 복잡도가 1억이 초과하여 불가능해 보인다.$($안 해봐서 모른다 의외로 될지도 굉장히 애매한 복잡도$)$ 하지만, N이 500 이하이므로 2배를 수행하는 선택이 10번 이상 나오면 값이 최소 1024$(=2^{10})$이므로 10번 이상의 2번 연산은 배제하면 되어..

https://www.acmicpc.net/problem/18276문제 분석 엣지마다 가중치가 존재하는 트리에서 부분트리가 가지는 트리의 엣지수 X 엣지의 가중치 최솟값이 최대가 되는 부분 트리를 구하는 문제이다. 단순히, 모든 부분 트리에 대해서 해당 값을 구하면 부분트리의 개수가 평균적으로 $n^2$에 비례하고 부분 트리 내 모든 노드를 순회해야 하므로($n/2$) 수 틀리면 $n^3$의 복잡도가 나오는 그다지 좋은 접근 방식은 아니다.  따라서, 부분 트리의 엣지수를 고정시키거나 엣지의 가중치 최솟값중 하나를 고정시키고 둘의 곱이 최대가 되게 끔 고정되지 않은 값은 그리디 하게 최적으로 접근하도록 두는 방식을 생각해야 한다. 1번째로, 트리의 엣지수를 고정시켜도 같은 트리의 엣지수를 가지는 부분트리..

https://www.acmicpc.net/problem/15166문제 분석 서로 같이 싣을 수 없는 약들을 고려했을 때, 좌우 화물의 무게 제한을 넘기지 않고 약을 싣을 수 있는지를 묻는 문제이다. 이를 해결하기 위해서 문제를 두 가지 조건으로 나누어 접근해야 한다.1. 무게를 고려하지 않았을 때 두 개로 나누는 것만으로 같이 싣으면 안 되는 약끼리 분리가 되는지ex) (1,2), (2,0), (0,1) 같이 있을 수 없는 쌍이라면 애초에 두 개만으로 는 분리가 불가능하다.2.  1번 조건을 만족한다면 좌우 무게까지 고려해서 두 개로 분리 가능 한지 1번째 조건에 대한 해결은 DFS로 사용하며 매깊이마다 달라지는 플래그를 사용해서  해결가능하다. 우선, 같이 싣으면 안 되는 쌍이 입력으로 들어왔을때 이..

https://www.acmicpc.net/problem/26015문제 분석 문제는 전날과 전전날의 스프를 같은 양으로 합쳐서 매일 새로운 스프를 만들때, N번째 날의 스프의 재료의 비율을 묻는 문제이다. 재료는 두가지 뿐이므로 첫번째 재료의 양만 구하면 나머지는 100에서 해당 재료를 빼면 된다. n번쨰 날 1번째 재료의 양과 2번째 재료의 양을 $A_n, B_n$이라 할때 문제는 다음과 같은 식을 만족한다.$A_n=\frac{A_{n-1}+A_{n-2}}{2}$$A_n+B_n=100$$A_1=100, A_2=0$오차범위는 $10^{-6}$ 여기서 n의 범위가 $[1,10^{18}]$이므로 0부터 순차적으로 A를 구하는 것은 어렵다. 따라서 가능한 접근 방식은 하단의 두가지이다. 문제 해결전략에서 두가..

https://www.acmicpc.net/problem/30547문제 분석 문제 설명에 앞서 그레이 코드 개념에 대해 간단히 설명하겠다. 그레이 코드는 일반 이진 코드와 다르게 앞뒤 전후의 숫자와 1비트만 다르게끔 10진수를 2진 코드로 표현하는 방식이다. 연속적인 변화에서 단일 비트만 변경되므로 오료나 오차 체크용으로 주로 사용되는 방식이다.10진 코드이진 코드그레이 코드000000000100010001200100011300110010401000110501010111601100101701110100810001100 문제는 이러한 그레이 코드를 변형하여 앞뒤 숫자와 단일비트가 아닌 짝수개의 비트만큼만 차이가 나도록 하는 modified gray code를 만드는 문제이다. 이때 짝수개의 비트만 다른 것..

https://www.acmicpc.net/problem/21636문제 분석 문제는 n과 k가 주어졌을 때 합이 N이 되게끔 숫자를 분할하고 각 숫자별로 k개의 색 중 하나를 배정했을 때 나올 수 있는 경우의 수를 구하는 문제이다. 단순히 합이 N이 되게끔 숫자를 분할하고 각 숫자별 개수에 따라 k개의 색을 배분하는 케이스를 구하면 된다. 합이 N이 되는 숫자의 조합은 단순히 DP를 통해서 조합의 수는 구할 수있지만 실제 각 숫자별 개수가 필요하여 다른 방식을 사용해야 한다. 브루트 포스로 모든 케이스를 고려하여 구해도 된다. N은 최대 17이므로 분할가능한 케이스는 순서를 고려해도 $2^{16} \approx 64000$의 크기를 가진다. 다만, 중복을 제거해야 하므로 백트래킹 방식을 사용하여 가장 큰..

https://www.acmicpc.net/problem/17497문제 분석 언뜻보기에는 DP라 생각할수있는 문제이지만, 초기값이 0으로 고정된다는 점에서 최상위 1비트(MSB 1bit)부터 N의 값과 맞추는 비트 연산을 그리디적인 관점에서 하는 문제라 볼수있다. 문제 접근은 간단하게 N을 이진수로 표현후 최상위 1비트 부터 값을 맞추고 2를 곱하여 시프팅하는 과정을 비트사이즈만큼 반복하면 된다. 다만, 1을 더하는게 아닌 2를 더하는 것인 만큼 N이 홀수일 때는 마지막에 나누기 연산을 추가로 하여 값을 맞춰줘야한다.문제 해결 전략 일단 GetButtonLog는 2가 아니라 1을 더한다고 가정하고 최상위 1비트 부터 최하위 비트까지 연산을 수행하는 함수이다. 실제 N과의 연산은 N이 짝수일때는 절반의 값..

https://www.acmicpc.net/problem/10640문제 분석 이번 문제는 3차원 공간에서 반지름이 1인 두 원이 주어졌을 때 두 원이 체인을 이루는 지를 물어보는 문제이다. 체인을 이룬다는 것은 두원이 서로 분리가 안되게끔 사슬처럼 얽혀있는 상태를 의미한다. 이때, 두원이 체인을 이루는 조건을  판별하는 것이 문제의 핵심이다. 체인을 이룬다는 것은 어떤 한 원의 일부가 다른 원의 내부에 존재한다는 특징을 가진다. 또한, 이러한 특징을 두 원 중 어떤 원을 기준으로 해도 성립해야 한다. 즉, 서로가 서로의 일부를 원 내부에 포함해야 한다. 어떤 원 내부의 점은 어떤 원을 이루는 평면과 다른 원의 두 교점이 될수 밖에 없다. 결국 어떤 원을 이루는 평면과 다른 원의 교점 중 하나가 어떤원내부..

https://www.acmicpc.net/problem/31478문제 분석 일반적인 정수론 문제이다. $A^{B^C}$와 $\frac {B^C} {A}$의 값에 $\text {mod 7}$을 적용한 값을 구하는 것이 핵심인 문제이다.  $A^{B^C}$의 경우 $B^C$가 매우 큰 값을 가지므로 페르마 소정리를 통해 식을 단순화 시킬 필요가 있다. 페르마 소정리를 따르면 소수인 p에 대해 p와 서로소인 a의 p-1승의 p에 대한 나머지는 1로 표현가능하다. 이때, 7은 소수이고 A는 [1,6]의 범위로 7과 항상 서로소인 값으로 페르마 소정리를 통해 다음의 식이 성립한다. $A^{B^C} \text { mod 7} = A^{(B^C \text { mod 6} )}\text { mod 7}$ 간략화한 식..