프로그래머스 N으로 표현 Swift

Source Code

 

---

Solution

 

해당 문제는 Dynamic Programming 에 관한 문제다.

 

처음엔 주어진 number로 dp를 만들어야 하나..? 라고 잘못 접근해서 풀기 어려웠는데

 

N의 갯수에 따라서 dp를 만드니 해결법이 나왔다.

 

먼저 N의 갯수에 따라서 모든 경우의 수를 미리 만들어서 배열에 넣었다.

 

우선 N이 1개부터 8개까지의 각 해결법이 필요한데 (가독성을 쉽게 하기 위해서 0번째도 값을 넣어줬다.)

 

먼저 N이 i개 일때 미리 그만큼의 N을 만들어줘서 넣어준다.

 

(말이 어려운데 만약 N이 5이고 i가 2개 라면 55를 넣어주고 i가 3개라면 555를 넣어준단 말이다)

 

N이 1개일땐 i개 1개 이므로 N을 넣어주고 다른 값은 없으므로 끝낸다.

 

N이 2개일땐 NN을 넣어주고 N이 1개일때의 값에 또 N이 1개일때의 값을 각 사칙연산별로 담을 수 있다.

 

N이 3개일땐 NNN을 넣고 N이 1개일때의 값과 N이 2개일때의 값을 각 사칙연산별로 담을 수 있다.

 

N이 4개일땐 NNNN을 넣고 N이 1개일때와 3개일때와 N이 2개일때와 2개일때를 각 사칙연산별로 담을 수 있다.

 

..... 이렇게 8개까지 반복하면 되는데 이것을 쉽게 배열로 표현하면

 

[[[1,1]],[[1,2]],[[1,3],[2,2]],[[1,4],[2,3]],[[1,5],[2,4],[3,3]],[[1,6],[2,5],[3,4]],[[1,7],[2,6],[3,5],[4,4]]]

 

같이 담을 수 있다.

 

이렇게 반복하다가 number에 해당되는 숫자가 나오면 N이 몇개인지 반환하면 된다.

 

주의할점은 a-b 와 b-a, 그리고 a/b 와 b/a는 값이 다르므로 두 값 모두 넣어줘야 한다는 점이다.

---

Problem

 

코딩테스트 연습 - N으로 표현

---

너무 풀이도 어렵고 별로 효율적으로 푼거같진 않다.

 

아래는 각 테스트별 걸린시간인데 4번과 5번 8번같은 경우 지나치게 시간이 많이 걸린다...

 

혹시 더 좋은 풀이 방법이 있으면 댓글로 알려주시면 감사하겠습니다!

 

또 좋은 풀이가 생각나면 수정해서 올리도록 하겠습니다.