알고리즘을 좋아하는 나

맨 위의 전구는 한 번씩 다 껐다 켜본다.

모든 전구는 2번 이상 건드리지 않는다.

대충 나오는 시간복잡도

O(2^N*N^2)

=> O(2^N)

N은 최대 18

풀이 방법 : 위의 전구가 켜져있으면 끈다.

근데 맨 위의 전구는 방법이 없다.

그래서 다 해본다.

완전 그래프는 모든 vertex가 연결돼있다.

출력하는건 사전순이다.

그래서 현재 vertex에서 사전순으로 제일 가까운것을 출력하면 된다.

그런데 N(N-1) 번째에는 1이 출력되고

N(N-2)번째에는 N이 출력된다.

이 방법을 이용하면 쉽게 풀이가능

dp로 풀었다. O(NM)

입력차례대로 위칸과 왼쪽칸과 왼쪽위 대각선 칸을 비교해서 가장 작은값 + 1로 새로운 정사각형을 만들 수 있다.

NYPC에서 풀었던 문제와 유사하다.

NYPC문제때는 급수를 이용해서 풀었었는데 틀리다고 나왔었다.

벽을 한 번 부신다!!

코드가 길지 않으니 설명은 없다.

용액의 특성값이 중복이 된다는 생각을 안하고 풀어서 1일이 걸렸다.

코드의 변화가 많이 있었는데

처음에는 순차적으로 검색하는걸 작성하다가 시간초과가 날 예상을 하고 안짰다.

다음에는 순차적으로 하는데 idx를 저장해서 그 idx만큼만 돌게했다. 시간초과

다음에는 l과 r을 두고 만나는 방식으로 했는데 틀렸다. 양수와 음수를 가지고 계산함.

다음에는 양수와 음수를 생각하지 않고 l과 r을 두고 만나는 방식을 사용함. (정답)

소수 계산은 아직 익숙하지가 않다.

그래서 다른 답들을 참고해봤는데, 문자열로 받아서 정수형으로 변환하고 처리하는게 많은거 같다.

또는 아주작은 숫자를 더해서 반올림 해주는거 같다.

     C(n+1) = C(n)/2     (C(n)이 짝수일 때)
            = 3*C(n)+1   (C(n)이 홀수일 때)

점화식이 이미 세워져있는걸 코드로 구현하면 된다.

pow를 이용해 자리를 변경해줬다.