프로그래머스(Java)-숫자의 표현

민지킴·2021년 3월 29일
0

프로그래머스

목록 보기
8/42
post-thumbnail

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12924

문제 풀이

주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다라는 정수론 정리가 있습니다.
라는 정수론 정리를 나중에 알았다.


    public static void main(String args[]) {
        int answer = 0;
        for (int i = 1; i <= num; i += 2) {
            if (num % i == 0) {
                answer++;
            }
        }
        return answer;
    }

이면 간단히 정리가 되는걸 몰랐기에
연속된 자연수의 합의 형태로 표현되는 조건을 홀수 짝수 나눠서 계산헀다.


코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        //k는 나누는 수, n은 몫
       
        //짝수 2n+1  4n+2  6n+3 ->   k x n + k/2
        // n, n+1
        // n-1 n n+1 n+2
        // n-2 n-1 n n+1 n+2 n+3
        //...
        
        //홀수 k x n 의 형태로 표현 가능
        
        //n의 약수 구하기
        for(int i=1; i<n; i++){
            int temp = n/i;
            int rest = n%i;
            //홀수
            if(i%2==1){
                if(rest==0){//나머지가 0이라면 k x n 형태인지 검증
                    if(temp > i/2){ //자연수 범위 내에서 가능한지 검증
                        // System.out.println(i);
                        answer++;  
                    } 
                        
                }else{
                    //해당x
                }
            //찍수
            }else{
                if(temp*i+i/2==n){ //k x n + k/2 와 n 이 같은지 검증
                    if(temp> (i/2)-1){ //자연수 범위내에서 가능한지 검증
                       // System.out.println(i);
                       answer++;
                    } 
                }

            }
        
        }
        
        return answer;
    }
}
profile
하루하루는 성실하게 인생 전체는 되는대로

0개의 댓글