[프로그래머스] N으로 표현
문제 설명
[ 생각하기 ]
1. N의 숫자만을 사용하여 사칙연산을 할 수 있고, 그 결과가 number 이 나오는 최소한의 N의 개수를 구하는 문제이다.
2. N의 개수의 범위가 1~8, N을 1~8번 사용해서 만들 수 있는 수 중 number이 나오는지 파악하면 된다.
- (N = 5라고 가정)
- 5의 개수가 1
- 5
- 5의 개수가 2
- 55
- 5+5, 5-5, 5*5, 5/5
- 5의 개수가 3
- 555
- [5의 개수가 1] (사칙연산) [5의 개수가 2]
- [5의 개수가 2] (사칙연산) [5의 개수가 1]
- 5의 개수가 4
- 5555
- [5의 개수가 1] (사칙연산) [5의 개수가 3]
- [5의 개수가 2] (사칙연산) [5의 개수가 2]
- [5의 개수가 3] (사칙연산) [5의 개수가 1]
- 5의 개수가 1
- 이게 도대체 뭐죠?!
- 3
- = 2+1
- = 1+2
- 4
- = 2+2
- = 1+3
- = 3+1
- 1을 제외한 숫자들은 N보다 작은 수들의 합으로 나타낼 수 있습니다.
- 이게 바로 DP!@!@!@!@! 드디어 규칙을 찾았다!
- 3
-
그렇다면, 왜 1+3, 3+1 따로따로 해주는 거죠?
- +. *는 위치를 바꿔도 계산의 결괏값이 바뀌지 않습니다.
- 하지만, - 와 / 연산은 위치에 따라 결과값이 변합니다.
- 그렇기 때문에, 1+3과 3+1 도 고려해주어야 합니다.
3. 이제, 이 과정을 코드로 옮기면 끝!
[ Python 코드 ]
def solution(N, number):
answer = -1
# 8개의 set초기화
s = [set() for x in range(8)]
#8개에 연속하는 N의 수 넣기
for i, x in enumerate(s, start=1):
x.add(int(str(N) * i))
for i in range(1, 8):
for j in range(i):
for op1 in s[j]:
for op2 in s[i-j-1]:
s[i].add(op1 + op2)
s[i].add(op1 - op2)
s[i].add(op1 * op2)
if op2 !=0:
s[i].add(op1 // op2)
if number in s[i]:
answer = i+1
break
return answer
[ 후기 ]
맨 처음 문제를 보고 중복 없는 순열을 구해서 계산을 할까 생각했다. 하지만, 자릿수가 정해져 있지 않다는 점, 고려해야 할 케이스가 많다는 점, 코드 짜기가 너무 복잡하다는 점으로 시도하지 못했다. (자릿수 별로 나눠서 순열을 구한다고 하더라도 char로 되어있는 배열을 다시 사칙연산이 되는 계산과정으로 풀어나가는 함수를 짜는 것도 만만치 않아 보였다.)
사실, 프로그래머스 연습문제로 나와있어서 DP로 푸는 문제라는 것을 알았음에도 불구하고 감이 안 잡혔다.
대체적으로 'DP로 풀어야겠다' 생각하는 문제들은 규칙성이 보였고 노트에 적다 보면 사칙연산이나 1차원, 2차원 배열로 풀 수 있는 문제가 많았다.
하지만, 이 문제는 거의 2시간을 보고 있었는데도, 규칙성이 보이지 않았다. (눈물..) 그래서 인터넷을 참고해서 풀었다.
난 아직 멀었다. 하지만 차근차근하면 할 수 있을 거다!
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42895
코딩테스트 연습 - N으로 표현
programmers.co.kr