프로그래머스 카카오 고득점 kit - 동적계획법(DP)

N으로 표현

• 문제
• 코드

푼 것, 배운 것

• 다른 분의 풀이를 보고 풀었다.
• 핵심은 숫자 1개로 만들수 있는 수, 2개로 만들 수 있는 수, 3개로.. 이렇게 차곡차곡 데이터를 채워나간다는 것
  • 숫자 2개로 만들 수 있는 수는
    • 연산자 없이 숫자2개를 이어붙인 수와
    • 숫자 1개로 만들 수 있는 수끼리 연산 한 것이다.
  • 숫자 2개로 만들 수 있는 수는
    • 연산자 없이 숫자3개를 이어붙인 수와
    • 숫자 1개로 만들 수 있는 수와 숫자 2개로 만들 수 있는 수 간에연산 한 것이다.
  • 숫자 N개로 만들 수 있는 수는
    • 연산자 없이 숫자 N개를 이어붙인 수와
    • 숫자 1개로 만들 수 있는 수와 숫자 N-1개로 만들 수 있는 수 간에 연산 한 것
    • 숫자 2개로 만들 수 있는 수와 숫자 N-2개로 만들 수 있는 수 간의 연산
      ...
    • 숫자 N-1개로 만들 수 있는 수와 숫자 1개로 만들 수 있는 수 간에 연산한 것

위에서 숫자 숫자 1개로 만들 수 있는 수와 숫자 N-1개로 만들 수 있는 수 간에 연산 한 것와 숫자 N-1개로 만들 수 있는 수와 숫자 1개로 만들 수 있는 수 간에 연산한 것은 다르다. 수의 순서에 따라서 - / 는 결과 값이 달라진다. 단 중복을 방지하기 위해 set()에 넣는다