프로그래머스[Java] - 숫자의 표현

 

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

 

 

코드

	public static int solution(int n) {
		int answer = 0;
		int startNum = 1;
		while(startNum <= n) {
			int sum = 0;
			for(int i=startNum; i<=n; i++) {
				sum += i;
				if(sum == n) {
					answer ++;
					break;
				}
                /*
				else if(sum > n)
					break;
                */
			}
			startNum ++;
		}
		return answer;
	}

 

풀이

n이 15일 경우 예로들면,,

1+2+3+4+5 = 15

4+5+6 = 15

7+8 = 15

15 = 15

총 네가지의 방법이 있다.

startNum 이 입력받은 n보다 작을때까지 반복했다.

(startNum은 더할때 가장 첫 숫자. 1+2+3+4+5 에서는 1, 4+5+6 에서는 4가 된다.)

 

for문에서 i를 startNum 부터시작해서 더해준다.

만약 sum이 n과 같다면, answer을 +1씩 하고 break통해 빠져나간다.

for문이 전부끝날시 startNum을 +1씩 증가시킨다.

 

 

위와 같이 풀고 제출하니 테스트케이스는 전부 맞는데 효율성에서 실패가 났다...

그래서 sum에 i값을 더하고, sum이 입력받은 n보다 커지면 그 이후는 판단할 필요가 없어서 빠져나와주었더니 통과를 했다.(위에서 주석친 부분 제거)

/*
else if(sum > n)
    break;
*/

 

 

 

다른 풀이

public class Expressions {

    public int expressions(int num) {
        int answer = 0;
        for (int i = 1; i <= num; i += 2) {
            if (num % i == 0) {
                answer++;
            }
        }
        return answer;
    }

    public static void main(String args[]) {
        Expressions expressions = new Expressions();
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(expressions.expressions(15));
    }
}

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

 

class Solution {
      public int solution(int n) {
          int answer = 0;
          
          for(int i=1; i<=n; i++) {
              int sum = 0;
              for(int j=i; j<=n; j++) {
                  sum += j;
                  
                  if(sum==n) {
                      answer++;
                      break;
                  } else if(sum>n) 
                      break;
              }
          }      
          return answer;
      }
    }