BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/6772
6772번: Choose Your Own Arithmetic
In Waterloo, you probably have seen some geese. How can you see geese with your calculator? Start with 6, add 7, multiply by 6, multiply by 8, add 7, multiply by 8, and multiply by 7, giving 35336. Then if you flip your calculator upside down, it says gEES
www.acmicpc.net
내가 작성한 코드
import sys
from collections import defaultdict
read = sys.stdin.readline
def read_data():
W = int(read().rstrip())
D = int(read().rstrip())
working_digit = []
for _ in range(D):
working_digit.append(int(read().rstrip()))
V = int(read().rstrip())
targets = []
for _ in range(V):
targets.append(int(read().rstrip()))
return W, D, sorted(working_digit, reverse=True), V, targets
def find_target(working_digit, value, target, depth, visited, crnt):
if depth == 0:
return value == target
for d in working_digit:
if not visited[depth][value*d] and find_target(working_digit, value*d, target, depth-1, visited, crnt+f"*{d}"):
return True
visited[depth][value*d] = True
if not visited[depth][value+d] and find_target(working_digit, value+d, target, depth-1, visited, crnt+f"+{d}"):
return True
visited[depth][value+d] = True
return False
def get_answer(working_digit, target, W):
visited = [defaultdict(bool) for _ in range(W+1)]
for d in working_digit:
if find_target(working_digit, d, target, W, visited, str(d)):
return "Y"
return "N"
W, D, working_digit, V, targets = read_data()
for target in targets:
print(get_answer(working_digit, target, W))
- 재귀+백트래킹
- digit 하나를 선택
- */+ 선택 후 다음 연산으로 재귀
- W번 연산 후 실패시 백트래킹
- DFS
- target을 완성하면 탐색 종료
- DP
- 이미 계산한 값을 저장
- 계산한 값이면 탐색하지 않음(prunning)
다른 사람이 작성한 코드
None
- 검색되지 않음
기억해야할 것
- 재귀 설계에 미숙함이 느껴짐
- substruct, parameter가 계속 바뀜
- visited를 depth마다 하지 않았었음
- 전체 재귀 과정이 머리에 그려지지 않아서 visited 설계를 잘못한듯
'코딩테스트' 카테고리의 다른 글
[백준][그리디] 보석 도둑 (0) | 2022.04.01 |
---|---|
[백준][재귀] 감소하는 수 (0) | 2022.04.01 |
[백준][슬라이딩윈도우] 달려라 홍준 (0) | 2022.03.29 |
[백준][재귀] 종이의 개수 (0) | 2022.03.24 |
[백준][세그먼트트리] 최솟값과 최댓값 (0) | 2022.03.23 |