[백준 13949] 쉬운 문제 (python)

https://www.acmicpc.net/problem/13949

13949번: 쉬운 문제

쉬운 문제 문제

식을 만족하는 임의의 n개의 양의 정수를 찾는 문제

수학적 개념에 대한 이해와 시도를 통해서 해결할 수 있었다

📌 문제 접근 포인트

1. 공식에 대해 생각해보자 a^2 + b^2 + c^2 = k*(ab+bc+ca) + 1 이란 공식을 변형시킬 방법을 생각해야 한다.
2. 임의로 a = 0, b = 1을 대입해보자. 그러면 c = k란 해를 항상 만족하는 해를 얻을 수 있고, 이점을 활용해보자.
3. 이거 하나만으론 일반 해를 얻을 수 없으니 하나의 일반해를 더 찾아보자. 식을 한쪽으로 전부 몰아주면 a*2 +k(b+c)a + b^2 + c^2+kbc-1 이란 식을 얻을 수 있는데, 이때 각 a, b,c에 대해 미분한 식 = 0에 대해서 생각해보면 이 a = k(b+c)/2 이렇게되고, 이차방정식이므로 이 해는 포물선의 정점이다. 이때, 그러면 이 포물선을 기점으로 좌 우의 해는 a와 a'이 되고, x점의 좌표를 연산으로 구해보면 (a+a')/2 = k(b+c)/2로 계산할 수 있다. 즉, a = k(b+c)-a'를 얻을 수 있게 되고, 이를 각 해로 넣으면 (k(b+c)-a, b, c) (a, k(a+c)-b,c) (a, b, k(a+b)-c) 라는 일반해를 각각 얻을 수 있게 된다.
4. 그럼 이제 이 일반해들을 이용해서 탐색을 진행해보자. 항상 모든 해를 만족하는 0,1,k를 set함수에 넣어주고, 겹치는 숫자를 제외해줄 check 리스트를 만들어 주었다.
5. 임시로 temp에 find를 저장하고, a,b,c에 대해 서로 다르고, 이미 나온 숫자도 아닌 상태일 때의 a,b,c를 하나씩 출력 및 제외해가면서, 3에서 얻은 일반해 3개를 각각 구해주기 위해 코드를 작성해주고 find를 갱신해서 n번 반복해주면 원하는 결과 값을 얻을 수 있었다.

⚙ 내가 푼 정답 코드

import sys
k,n = map (int, sys.stdin.readline().split())
check = [0]
find = set() # a = 0, b = 1 일때 항상 0, 1 ,k란 해를 만족하므로
find.add((0,1,k))

while n:
  temp = find.copy() # 현재 find를 temp에 복사
  for a, b, c in find: # 찾아보자
    if a != b and b != c: # 둘이 서로 수 이므로
      if a not in check and b not in check and c not in check: # 이미 나온 값도 아니면
        check += [a,b,c] # 나중에 빼야하니 체크
        print(a,b,c) # 이 때의 a,b,c 출력
        n -= 1 # 1씩 줄여가보자
        if n == 0: # n이 0이 되면
          break #끝내!
      for _ in range(3): # 3번의 반복 (a,b,c 각각에 대해 미분해보자)
        x = k * (a + b) - c # 미분 했을때 정점 (a,b,c 순서대로)
        if x >= 0: # 만약 정점이 0보다 크면
          temp.add(tuple(sorted([a,b,x]))) # 임시 값에 저장해
        a, b, c = b, c, a # 다른 3점 정점 찾아보자
  find = temp # find 갱신