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

풀이

연속된 자연수들의 합으로 자연수 n을 만들어라

 

완전탐색 -> 시간 초과

1,2,3... 이런식으로 더해나가다가 n이 되면 count++

다음 숫자는 2부터 시작, 3부터 시작 ... 더해서 n이되면 count++, n (자기자신) count++

간단하게 이중 for문으로 구현

function solution(n) {
  let count=0
  for (let i = 1; i <= n; i++) {
    let hap=0
    for (let j = i; j <= n; j++) {
      hap+=j
      if(hap===n){
        count++
        break
      }
      else if(hap>n) break
    }
  }
  return count
}

 

연속된 자연수

-> n이 15일때 연속된 자연수의 합 중 가장 큰 자연수(자기 자신 제외)의 조합은 7+8

즉, 최대 범위는 -> n/2

 

자기자신을 포함하기 때문에 count에 미리 1을 주고 풀었다

재귀와 합쳐서 만든 2번째 풀이 -> 통과

function solution(n) {
  let count=1
  const helper=(num,sum)=>{
    if(sum===n) count++
    else if(sum>n) return
    return helper(num+1,sum+num)
  }
  for (let i = 1; i <= n/2; i++) {
    helper(i,0)
  }
  return count
}

 

 

 

 

 

직관적인 풀이라고 생각되서 설명을 생략하겠다