🚀궤도사령부(궤도)

n개의 숫자의 합이 x가 되는 경우를 찾는 문제

궤도

우와와앙

24.02.24

취미삼아 코딩하고 노는데

어제 침하하 보다가 노노그램 이야기가 나오길래

갑자기 노노그램 푸는 기능을 스스로 만들어 보고 싶어져서

어제부터 머리를 쥐어싸매고 있는데요

어떻게 할까 생각하다가

노노그램을 row(행)과 column(열) 로 두고

row를 공배블록과 칠해진블록의 결합으로 구성해서 공배블록의 길이를 바꿔가면서 모든 패턴을 생성 한 후에,

그렇게 해서 생성된 패턴들을 column 방향으로 읽어서 생성되는 숫자를 문제에 주어진 column 수와 비교해서 일치하는 패턴을 발견하는 방식으로 풀어보려구요

좀 노가다스러운 방식이긴 한데 일단 작동하게 해 놓고 효율을 개선할 방법을 궁리해 보려구요

공배블록의 길이를 바꿔가면서 모든 패턴을 생성하려다 보니까

n개 숫자의 합이 x가 되는 경우를 모두 찾아야 되더라구요

수학은 잼병이라.. n개 숫자의 합이 x가 되는 경우(n>=0, x>=0)를 찾는 효율적인 방법이 정립된게 있을까요?

우와와앙 글쓴이

24.02.24

아 재귀함수를 쓰면 될 것 같네요...

오니솝터

24.02.24

백트래킹 하세요~

우와와앙 글쓴이

24.02.24

네 좀전에 완성했는데 테스트해보니 5*5 정도는 빨리 푸는데 10*10 하니까 너무 오래 걸려서 터미널이 끊어버리네요. 효율을 올릴 방법들을 찾아봐야겠어요

정수론민수

24.02.26

분할을 이용할 수 있겠네요. 정수론에서 'n의 분할'은 합이 n이 되는 자연수의 모임들의 개수를 말합니다. 예컨대 5는 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1, 총 7개의 경우의 수가 있어 5의 분할은 7이죠.

작성자분께서 말씀하신 질문은 제한 분할(restricted partition)을 말합니다.

위키피디아: https://en.wikipedia.org/wiki/Integer_partition 에서 Restricted part size or number of parts 챕터에서 확인하실 수 있습니다. 여기에 k개의 자연수의 합이 n이 되는 경우의 수를 p_k(n)이라 표기하는데, 아쉽게도 정확히 알려진 공식은 없습니다만 재귀적으로 정의할 수는 있습니다.

정수론민수

24.02.26

재귀적으로 정의하는 방법은 다음과 같습니다.

p_0(0) = 1,

k와 n 중 하나만 0일 시 p_k(n) = 0

해당 초기조건을 기반으로 p_k(n)은 다음과 같이 구해질 수 있다.

p_k(n) = p_k(n-k) + p_{k-1}(n-1).

우와와앙 글쓴이

24.02.29

감사합니다 만든 함수가 이런 방식 써서 만든거라 정답 맞춘 으쓱한 기분이네요 ㅋㅋ 모든 케이스를 구하는 함수에요.

@정수론민수