블로그 이사합니다.

새로운 주소는 sarojaba.com 입니다.

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

문제 출처: http://rucifer.tistory.com/entry/Algorithm-%EB%AC%B8%EC%A0%9C-01-%EC%A0%95%EC%88%98-%EC%86%8C%EC%9D%B8%EC%88%98-%EB%B6%84%ED%95%B4

정수 소인수 분해 문제의 재귀 풀이: http://sarojaba.tistory.com/233

위 포스트에서 스마트 돌고래 님께서 동적계획법으로 풀어달라는 요청이 있었습니다. 동적계획법을 적용하기 좋은 문제라고 생각되어 적당히 풀어서 풀이를 올립니다.

사용 언어는 Java이고, 파일 입출력은 생략하였고, 샘플 케이스만 만족시켰습니다. 나름 충실히 주석 적어놓았습니만 궁금하신 부분은 언제든 질문하시기 바랍니다. 또한 많은 지적 부탁드립니다.

위키피디아에 소인수 분해 문제에 대한 다양한 알고리즘이 존재하였습니다. 시간이 된다면 공부해서 올리도록 하겠습니다.

main과 solve 메소드는 앞선 포스트의 코드와 내용이 동일합니다. factor 메소드만 보셔도 될듯합니다. 이해하기 쉽게 각 케이스별로 배열을 재계산하게 코딩하였지만 실제 사용한다면 모든 케이스가 배열을 공유하여 계산량을 줄일 수 있도록 전역으로 두시기 바랍니다.

###java
public class PrimeFactorUsingDynamic {
public static void main(String[] args) {

solve(45);
solve(12);
solve(67);
solve(100);
solve(200);
}

/**
* 문제를 푼다.
*
* @param input
* 입력값
*/
public static void solve(int input) {

// 소인수를 더한다.
int output = factor(input);

// 입력값과 계산값이 같으면 소수이다.
boolean isPrime = (output == input);

if (isPrime) {
System.out.println("Prime Number");
} else {
System.out.println(output);
}
}

/**
* 소인수의 합을 구한다. 단, 입력값이 소수인 경우 입력값과 출력값은 같다.
*
* @param n
* 정수 ex) 12 = 2*2*3
* @return 소인수의 합 ex) 7 = 2+2+3
*/
public static int factor(int n) {

// 계산된 값들을 저장할 배열.
// 0과 1은 빈칸으로 두고 사용하지 않는다.
int[] arr = new int[n + 1];

// 2부터 인자로 받은 숫자까지 순차적으로 계산해간다.
for (int i = 2; i < n + 1; i++) {

// 몫을 저장하기 위한 변수
int t = i;

// 몫이 1이라는 뜻은 계산이 끝났다는 의미이다.
while (t != 1) {

// 인수는 2부터 시작한다.
int f = 2;

// 정확히 나누어 떨어지지 않으면 인수를 하나씩 증가시킨다.
while (t % f != 0) {
f++;
}

// 나누어 떨어지는 인수로 나눈다.
t /= f;

// 혹시 이전에 미리 계산된 값이 있으면 사용한다.
if (arr[t] != 0) {
arr[i] = f + arr[t];
break;
}

// 인수를 더해서 저장한다.
arr[i] += f;
}
}

// 모든 계산이 끝나면 배열의 마지막 수가 입력값의 소인수를 모두 더한 값이다.
return arr[n];
}
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.