[백준][재귀] Choose Your Own Arithmetic

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/6772

6772번: Choose Your Own Arithmetic

 

내가 작성한 코드

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 설계를 잘못한듯