얄루의 개발일기🥑

문제 주어진 수를 문자로 매칭해서 해당 수를 문자로 바꿔라 문제 풀이 def DFS(L, p): global cnt if L == n: cnt += 1 for i in range(p): print(chr(res[i] +64), end=" ") print() else: for i in range(1,27): if code[L] == i: res[p] = i DFS(L+1, p+1) elif i>=10 and code[L] == i//10 and code[L+1] == i%10: res[p] = i DFS(L+2, p+1) if __name__ =="__main__": code = list(map(int,input())) n = len(code) code.insert(n,-1) res = [0] * (n+3..

문제 3명에게 n개의 동전을 나눠줄 때 제일 큰 금액을 가진자와 제일 작은 금액을 가진자의 차가 최소가 되게 하라 문제 풀이 def DFS(L): global res if L == n: Min = max(abc) - min(abc) if Min < res: tmp = set() for x in abc: tmp.add(x) if len(tmp) == 3: res = Min else: for i in range(3): abc[i] += coin[L] DFS(L+1) #해당 작업이 끝나고 다시 윗 노드로 온 상황이기에 해당 값을 빼주어야 한다.(안 그러면 누적되기 때문) abc[i] -= coin[L] if __name__ == "__main__": n = int(input()) coin = [int(inpu..

문제 주어진 금액에 맞게 동전들을 사용한 경우가 몇 번이나 있는지 출력해라 문제 풀이 def DFS(L,s): global res if L == k: if s == T: res += 1 else: for i in range(coin[L][1]+1): DFS(L+1,s + (coin[L][0]*i)) if __name__ == "__main__": T = int(input()) #지폐의 금액 k = int(input()) #동전의 가지 수 res = 0 coin = [] for i in range(k): #동전 금액, 갯수 a, b = map(int,input().split()) coin.append([a,b]) DFS(0,0) print(res) 주어진 동전의 갯수만큼 DFS를 돌며 진행한다.

풀이 def DFS(L, money, day): global res if day > n: return if day == n: if res < money: res = money else: DFS(L+1, money + schedule[day][1], day + schedule[day][0]) DFS(L+1, money, day+1) if __name__ =="__main__": n = int(input()) schedule = [] for _ in range(n): a, b = map(int,input().split()) schedule.append([a,b]) res = -2147000000 DFS(0,0,0) print(res) 설명 schedule.append([a,b]) - schedule[변수][..

def DFS(L, s,ts): global res if ts > m: return if L == n: if res < s: res = s else: DFS(L+1, s + a[L][0], ts + a[L][1]) DFS(L+1, s, ts) if __name__ =="__main__": n, m = map(int,input().split()) res = -2174000000 score = [] for i in range(n): a, b = map(int,input().split()) score.append([a,b]) a= sorted(score,key=lambda x:x[1]) a.sort(reverse=True) DFS(0,0,0) print(res) 상태 트리를 사용해서 풀었다. 종료 조건 해당 ..

문제 문제 풀이 n, m = map(int,input().split()) matrix = [[0]*(n+1) for _ in range(n+1)] for i in range(m): a, b, c = map(int,input().split()) if matrix[a][b] == 0: matrix[a][b] = c else: if matrix[a][b] < c: matrix[a][b] = c for i in range(1, n+1): for j in range(1, n+1): print(matrix[i][j], end =" ") print()

def DFS(L,s): global cnt if L == m: for i in res: print(i, end =" ") print() cnt += 1 else: for i in range(s, n+1): res[L] = i DFS(L+1, i+1) if __name__ == "__main__": n, m = map(int,input().split()) cnt = 0 res = [0] * m DFS(0,1) print(cnt) 앞에 들어간 숫자는 중복해서 나오면 안 되기 때문에 s로 +1 해주며 진행해준다.

문제 1부터 n까지의 m개의 순열을 구하라 문제 풀이 def DFS(L): global cnt if L == m: for i in range(m): print(res[i],end =" ") print() cnt += 1 else: for i in range(1, n+1): if ch[i] == 0: ch[i] = 1 res[L] = i DFS(L+1) ch[i] = 0 if __name__ == "__main__": n, m = map(int,input().split()) res = [0] * n ch = [0] * (n+1) cnt = 0 DFS(0) print(cnt) 중복 수열과 다르게 이번엔 중복된 값 없이 진행해야 하기에 check를 위한 리스트를 만들어 해당 노드가 앞에 나온다면 다시 나오지 ..

문제 상태 트리의 경우엔 이진 트리로 선택하거나 선택하지 않거나의 문제로 가지가 뻗어나가는 형태였다. 그러나 이 경우엔 여러 가닥의 가지가 뻗는 트리의 형태를 보여준다. 1부터 N까지 번호가 적힌 구슬이 있을 때 중복을 허락하는 조건으로 M개를 뽑아 일렬로 나열하는 방법을 모두 출력하라 문제 풀이 def DFS(L): global cnt if L == m: for i in range(m): print(res[i], end=" ") print() cnt += 1 else: for i in range(1, n+1): res[L] = i DFS(L+1) if __name__ == "__main__": n,m = map(int,input().split()) res = [0] * m cnt = 0 DFS(0) p..

def DFS(L, sum, tsum): global result if sum+(total-tsum)c: return if L==n: if sum>result: result=sum else: DFS(L+1, sum+a[L], tsum+a[L]) DFS(L+1, sum, tsum+a[L]) if __name__=="__main__": c, n=map(int, input().split()) a=[int(input()) for _ in range(n)] result=-2147000000 total=sum(a) DFS(0, 0, 0) print(result) 종료 조건을 더 늘려서 속도를 개선했다. 해당 res에 들어간 값보다 아래 가지를 더해도 값이 더 가까워지지 않을 땐 res를 사용하도록 하는 것이다.