어느날 우리애가 풀어보라면 들고 왔습니다. 선생님이 내줬다는 문제인데요....
과연 풀려면 어떻게 할까 생각해보다가, 오랜만에 PC로 풀어볼려고 마음먹었습니다. 정리하자면 아래와 같은 문제입니다.
문제) 1~9까지 서로 다른 숫자를 사용해 들어갈 숫자를 완성하세요.
A B
X C
--------
D E
+ F G
--------
H I
이중에 힌트로 B=7,I=3가 주어졌다고 합니다.
힌트 없이 풀어보도록 하겠습니다.
각각의 값은 중복이 되지 않으므로 순열이라고 보면됩니다.
방법은 A=1...9까지 선택하고 B=1....9 까지 선택하고... 이런식으로 I까지 선택한 후 이전에 선택된 값이라면 무시하고 식이 맞는지 확인하는 방법으로 구해보았습니다.
여러개의 루프를 사용하면서 안쪽에서 다시 루프를 사용하고 아래와 같은 코드에 의해 이미 선택된 값이라면 선택이 되지 않도록 합니다.
if(usedflag[b])continue;
여러개의 루프를 사용하는 방법:
package testProject;
public class Test3 {
public static void main(String[] args) {
test1();
}
private static void test1() {
boolean usedflag[]={false,false,false,false,false,false,false,false,false,false};
for(int a=1;a<=9;a++){
usedflag[a]=true;
for(int b=1;b<=9;b++){
if(usedflag[b])continue;
usedflag[b]=true;
for(int c=1;c<=9;c++){
if(usedflag[c])continue;
usedflag[c]=true;
for(int d=1;d<=9;d++){
if(usedflag[d])continue;
usedflag[d]=true;
for(int e=1;e<=9;e++){
if(usedflag[e])continue;
usedflag[e]=true;
for(int f=1;f<=9;f++){
if(usedflag[f])continue;
usedflag[f]=true;
for(int g=1;g<=9;g++){
if(usedflag[g])continue;
usedflag[g]=true;
for(int h=1;h<=9;h++){
if(usedflag[h])continue;
usedflag[h]=true;
for(int i=1;i<=9;i++){
if(usedflag[i])continue;
usedflag[i]=true;
if(((a*10+b)*c)==((d*10)+e)){
if(((d*10)+e)+((f*10)+g)==(h*10)+i){
System.out.println("a="+a+",b="+b+",c="+c+",d="+d+",e="+e+",f="+f+",g="+g+",h="+h+",i="+i);
}
}
usedflag[i]=false;
}
usedflag[h]=false;
}
usedflag[g]=false;
}
usedflag[f]=false;
}
usedflag[e]=false;
}
usedflag[d]=false;
}
usedflag[c]=false;
}
usedflag[b]=false;
}
usedflag[a]=false;
}
}
}
결과:
a=1,b=7,c=4,d=6,e=8,f=2,g=5,h=9,i=3
위 방법대로 할경우 문제가 있습니다. 많은 변수를 사용하게 되면 굉장히 코드도 길어지고 그러다보면 실 수 할 수도 있게 됩니다.
그렇다면 코드의 중복되는 부분을 함수로 만들어서 호출해주는 방법을 고민하게 됩니다.
기본적으로 구현은 자기자신을 호출해주는 재귀부와 조건이 맞으면 더이상 재귀를 동작 안하게 하는 두 부분으로 구성됩니다.
재귀부:
for(int i=1;i<=9;i++){
test2(depth+1,usedflag,selected);
}
더 이상 재귀를 동작 안하게 하는 부분:
if(depth == 9) {
return;
}
재귀를 동작 안하게 하려면 얼마나 호출되었는지 관리가 필요합니다. 여기에서는 depth 변수를 이용하여 관리를 하고(자신을 호출시 depth+1 사용) 특정 조건에 맞으면 더 이상의 재귀 동작을 멈추게 합니다. (if(depth==XX) return 조건 사용)
아래는 구현한 내용입니다.
재귀 호출을 이용한 방법:
package testProject;
public class Test3 {
public static void main(String[] args) {
boolean usedflag[]={false,false,false,false,false,false,false,false,false,false};
int selected[]={-1,-1,-1,-1,-1,-1,-1,-1,-1};
test2(0, usedflag, selected);
}
private static void test2(int depth, boolean usedflag[], int selected[])
{
if(depth == 9) {
if(((selected[0]*10+selected[1])*selected[2])==((selected[3]*10)+selected[4])){
if(((selected[3]*10)+selected[4])+((selected[5]*10)+selected[6])==(selected[7]*10)+selected[8]){
System.out.println("a="+selected[0]+",b="+selected[1]+",c="+selected[2]+",d="+selected[3]+",e="+selected[4]+",f="+selected[5]+",g="+selected[6]+",h="+selected[7]+",i="+selected[8]);
}
}
return;
}
for(int i=1;i<=9;i++){
if( usedflag[i] ) continue;
usedflag[i]=true;
selected[depth]=i;
test2(depth+1,usedflag,selected);
usedflag[i]=false;
}
}
}
순열에 대한 자세한 내용은 아래 링크를 확인해보세요.
http://swlock.blogspot.kr/2016/11/permutation-combination-algorithm_13.html
