60. 부정방정식 풀이 알고리즘

1. 개요

드디어 부정방정식 알고리즘 풀이다.

이 풀이는 무척 간단하다.

하지만 난 몰랐다.

멍청이다 난.

먼저 부정방정식이란 이런 형태를 말한다.

x0+x1+x2+x3+ ... xn = K

이런 식이 있을 때, K가 주어질 때, 이를 만족하는 x0, x1, x2, x3 ... xn을 찾는 것이다.

항상 궁금했었다. 이 부정방정식 풀이를 어떻게 해나가는지.

특히, 예전에 어머니가 일하는 시는 복지회관의 설문 조사에서 값을 정해주고 통계를 내달라는 부탁을 받았다.

왜 이걸 직접 받아야지, 마음대로 조작하냐고물어보니까,

거기 복지회관 분들이 시각장애인분들 도움주는 복지회관이고, 또한 연세가 많으셔서 이 설문받기가 어렵다고 한다.

물어봐서 답변하는 방식으로는 다들 좋다고만 하셔서 오히려 이렇게 직접 일정 기준을 만들어놓고 하는게 신뢰성있다고 한다.

그래서 뭐 어쩔 수 없이, 이 통계를 내려고하는데 일단 나는 엑셀을 못한다.

수학적으로 하나하나 접근하려고 하니, 머리가 안돌아갔다.

여러 번 고심하다 그냥 프로그램 만들어서 다 돌려버렸다.

하지만 그 때 만들었던 방식은 5중첩 for 루프 방식이었다.

5점 4점 3점 2점 1점 식으로 다 돌면서, 점수를 만점에서 95% 유지할 수 있는 조건들을 추출했다.

결과야 잘 나왔지만, 마음에 안들었다.

5중첩 for 루프라니.

코딩을 막 시작할 때나 쓰던 방법이었다.

그래서 어떻게하면 부정방정식을 깔끔하게 풀 수 있는지 궁금했는데, 오늘에서야 조금 더 깊게 알아간다.

결국 전수조사밖에 답이 없긴한데, 각 부정방정식에 걸린 조건에 따라 조금씩 최적화를 시킬 수 있다고 생각한다.

2. 문제

미지수 x의 개수 N을 입력하고, 구해야 할 값 K를 입력했을 때, 가능한 모든 경우의 수를 구하고 그에 따른 값을 출력하시오.

(순서를 구분하는 경우, 순서를 구분하지 않는 경우 두 가지 방식 모두 풀이하시오.)

3. 코드 및 출력

3-1) 순서를 구분하는 모든 부정방정식 풀이

3-2) 순서를 구분하지 않는 모든 부정방정식 풀이

3-3) 합계가 K와 일치 판단 알고리즘

3-4) 출력

4. 정리

이렇게 부정방정식 풀이의 아주 기초 알고리즘을 알아냈다. 다만, 이 방식은 K의 값이 높아지면 어마어마한 수행속도가

걸린다. 왜냐하면 재귀적 풀이니까. 퍼즐에서 부정방정식과 비슷한 방식의 퍼즐이 있다. 복면산 퍼즐이라는 방식인데

흔히 인적성 검사에서 많이 보던 문제 유형이다. 나중에 이 복면산 퍼즐 알고리즘을 작성하면서 부정방정식에 대해

더 정리하자. 배고프다. 점심먹자.