23.03.07 파이썬 코딩 퀴즈#185 N으로 표현(프로그래머스 스쿨)

이번 문제는 N으로 표현 문제이다.

오랜만에 설명이 짧고 명쾌한 문제인것 같다.

1~9 사이의 N이 주어질때 number를 만들수 있는 사칙연산을 표현 한 수식 중 N의 사용횟수의 최솟값을 찾아 return 해야 한다. 한가지 주의할 사항은 최솟값이 8보다 크면 -1을 return 해야 한다.

 

설명은 짧지만, 문제 자체는 난이도가 있어 보인다.

 

먼저 N에 따라 만들 수 있는 수를 확인해야 한다.

입출력 예제 1에서 사용한 5를 기준으로 살펴보자.

먼저 1을 만드려면 5/5 가 되어야 한다. 따라서 2회 사용된다.

2를 만드려면 1+1 또는 10/5 가 필요하다. 따라서 (5+5)/5 가 된다. 3회 사용

여기서 한가지 주의할 점은 모든 사칙연산을 사용한다는 점이고, 나머지는 무시한다는 점이다.

 

반대로 사용한 횟수를 기준으로 살펴보자

5를 한번 사용하는건 5 하나 밖에 없다

5를 두 번 사용하면, 5+5, 5-5, 5*5, 5/5, 55 총 5가지 연산이 나온다.

5를 세 번 사용하면... 굉장히 복잡해 진다. 그 이유는 ()에 의해 더 많은 같은 수식이라도 더 많은 경우의 수가 생기기 때문이다. 하지만 이러한 연산은 컴퓨터가 할 일이지 사람이 할 일은 아니다. 걱정하지 말자.

 

먼저 dp 배열을 만들어 숫자 N을 1개부터 7개까지 사용해서 만들 수 있는 수들을 저장한다.

기본적으로 N, NN, NNN 은 연산 없이도 만들수 있기 때문에, dp 배열에 넣어준다.

그리고 이제 4중 반복문을 돌게 되는데, 어려운 부분은 없다.

먼저 i 값은 순회할 dp 의 index 이다. 1개(index 0)로 만들 수 있는 경우의 수는 오직 N 자신뿐이기 때문에 탐색범위는 1~8 까지가 된다. 그리고 j 는 i 값을 기준으로 반복한다.

이 말은 만약 i 가 1이라면, j 는 0 이 되고, 결과적으로 dp[j] 는 N을 1개 쓰는경우, dp[i-j-1] 도 N을 1개 쓰는 경우가 된다.

따라서 dp[i] N을 2개 쓰는 경우에 해당 조합으로 연산에 의한 숫자들이 추가가 되며, set()에 의해 중복된 숫자는 들어가지 않는다. 그리고 zero division error를 방지하기 위해 조건문을 사용하였다.

또한 dp[i]에 number가 존재할 경우 해당 조합은 최소조합이 되므로, 조건문에 의해 number가 존재하는지 확인한 뒤 있는 경우라면 i값에 1을 더한 값을 없다면 answer 을 -1 값으로 해준다. 

i = 1 이라면, dp[0] 과 dp[0]을 (1개 사용한 경우 x 1개 사용한 경우)

i = 2라면, dp[0]과 dp[1]  (1개 사용한 경우 x 2개 사용한 경우) dp[1]과 dp[0] (2개 사용한 경우 x 1개 사용한 경우) 를 연산하게 되는데, 1x2와 2x1 은 괄호에 의해 우선순위가 정해지는걸 계산한 경우이므로 엄연히 다른 값이다.