[백준] [DFS] 20444. 색종이와 가위

20444. 색종이와 가위

20444번: 색종이와 가위

 

• 내 풀이

#n번의 가위질로 k개의 색종이를 만들수있는지
#yes, no

n,k=map(int,input().split())
num=1
result=[]
answer=[]
#세로 한줄로 잘라나가지는 경우
  #한개의 열을 자른다
  #행 개수*2+ (열개수-1)*행 개수 
#가로 한줄로 잘라지는 경우
  #한개의 행을 자른다
  #열 개수*2 + (행개수-1)*열개수

#재귀인가.. 큐인가
#n번이라는 기저조건이 있으니 재귀아닐까?

def dfs(depth, r,c):
    if depth==n:
        print(result)
        return result

    num=0
    #세로한줄로 자르는 경우
    num=r*2+ (c-1)*r
    result.append(num)
    #행은 그대로, 열은 한개+1
    dfs(depth+1, r, c+1)

    num=0
    #가로한줄로 자르는 경우
    num= c*2+ (r-1)*c
    result.append(num)
    dfs(depth+1, r+1, c)
    
answer.append(dfs(0,1,1))

if k in result:
      print("yes")
else:
      print("no")

- 풀이 수정
- 테케는 맞는데 recursion error

#n번의 가위질로 k개의 색종이를 만들수있는지
#yes, no

n,k=map(int,input().split())
result=[]
#세로 한줄로 잘라나가지는 경우
  #한개의 열을 자른다
  #행 개수*2+ (열개수-1)*행 개수 
#가로 한줄로 잘라지는 경우
  #한개의 행을 자른다
  #열 개수*2 + (행개수-1)*열개수

#재귀인가.. 큐인가
#n번이라는 기저조건이 있으니 재귀아닐까?

def dfs(depth, r,c):
    if depth==n:
        result.append(r*2+ (c-1)*r)
        result.append(c*2+ (r-1)*c)
        return

    #세로 한줄 자르는 경우
    #행은 그대로, 열은 한개+1
    dfs(depth+1, r, c+1)

    #가로한줄로 자르는 경우
    dfs(depth+1, r+1, c)
    
dfs(1,1,1)

if k in result:
      print("yes")
else:
      print("no")