기본적인 알고리즘 문제 풀기(Project Euler) - 2

기본적인 알고리즘 문제 풀기 - 2

문제 4. 

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method4();
    }
}
 
class MyClass1{
    // 문제4.     
    // 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
    // 두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
    // 세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?
     public void method4(){
         int intValue1;
         String stringValue1;
         ArrayList<String> arraylist = new ArrayList<String>();
        for(int i=1; i<1000; i++){
            for(int j=1; j<1000; j++){
//                System.out.println("i값: "+i+"x"+j+"="+i*j);
                intValue1 = i*j;
                stringValue1 =Integer.toString(intValue1);
                
                if(stringValue1.length() % 2 == 0){
                    if(stringValue1.length() == 2){
                        if(stringValue1.charAt(0) == stringValue1.charAt(1)){
                            System.out.println("2자리 대칭수: "+stringValue1);
                        }
                    }
                    if(stringValue1.length() == 4){ // 10 01
                        if(stringValue1.substring(0,2).equals(stringValue1.substring(3,4)+stringValue1.substring(2,3))){
                            System.out.println("4자리 대칭수: "+stringValue1);
                        }
                    }
                    if(stringValue1.length() == 6){
                        if(stringValue1.substring(0,3).equals(stringValue1.substring(5,6)+stringValue1.substring(4,5)+stringValue1.substring(3,4))){
                            System.out.println("6자리 대칭수: "+stringValue1);
                            arraylist.add(stringValue1);
                        }
                    }
                }
            }
        }        
        System.out.println("3자리 대칭수 중 가장 큰값은: "+Collections.max(arraylist));
    }
}

출력결과

문제 5.

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 

접근방법 5-1. if문 중첩방법

package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method5();
    }
}
 
 
class MyClass1{
        
     // 문제5 접근방법1.
     // 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
     // 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?     
     public void method5(){
         int n = 10000;
         for(int i=2; i<=10;){
             if(n % i == 0){// 2
                 i++;
                 if(n % i == 0){ // 3     
                     i++;
                     if(n % i == 0){ // 4          
                         i++;
                          if(n % i == 0){ // 5          
                              i++;
                               if(n % i == 0){ // 6          
                                   i++;
                                    if(n % i == 0){ // 7          
                                        i++;
                                        if(n % i == 0){ // 8        
                                            i++;
                                            if(n % i == 0){ // 9
                                                i++;
                                                if(n % i == 0){ // 10
                                                    System.out.println("1부터 10까지 나눠지는 수: "+n);
                                                    i++;
                                                }
                                            }
                                        }
                                    }
                                }
                           }
                      }
                 }
             }
             if(n>1){
                 n = n-1;                 
             }
             i = 2;
         }
     }
}

출력결과

접근방법 5-2. 메소드 호출방법

package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method5A(999999999,2);
    }
}
 
 
class MyClass1{
    
     // 문제5 접근방법2.
     // 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
     // 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?     
     // n= 10000, i= 2
     public void method5A(int n, int i){
         while(n>1){
             if(n%i==0){ // 1000 % 2 == 0
                 i++; // 3
                 if(n > 1){
                     method5B(n, i);
                 }
                 if(i==20){
                     System.out.println("1부터 20까지 나눠지는 수: "+n);
                 }
             }else{
                 if(n>1){
                     n = n-1;
                 }
                 i = 2;  
             }             
         }
     }     
     
     public void method5B(int n, int i){     
         if (n % i == 0 ){
            i++;
        }
     }
}
 

출력결과

문제 6. 

1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).

1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2+9^2+10^2

1+4+9+16+25+36+49+64+81+100 = 385

1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).

(1 + 2 + ... + 10)^2 = 552 = 3025

따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.

그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?

package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method6();
    }
}
 
 
class MyClass1{
 
    // 1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).
    // 1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2+9^2+10^2
    // 1+4+9+16+25+36+49+64+81+100 = 385
    // 1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).
    // (1 + 2 + ... + 10)^2 = 552 = 3025
    // 따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.
    // 그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?     
     
     public void method6(){
         int squareSum = 0;
         int sumSquare = 0;
         int subtractSquare = 0;
         for(int i=1; i<=100; i++){
             squareSum += i * i; // 1 * 1 // 2* (2*2) 3*3 4*4
         }
         System.out.println("제곱의 합: "+squareSum);
         for(int i=1; i<=100; i++){
             sumSquare += i;
         }
         sumSquare *= sumSquare;
         System.out.println("합의 제곱: "+sumSquare);
         subtractSquare= sumSquare - squareSum;
         System.out.println("합의제곱-제곱의합: "+subtractSquare);
     }     
     
}

출력결과