꾸준하게 거북이처럼

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net DFS 구현 문제로 풀 수 있으며, 시간 초과를 유의해야하는 문제다. 최대 3개의 사다리를 추가로 놓을 수 있으며, 탐색을 할 때 이미 탐색 중인 개수가 3개이상 또는, 업데이트된 추가된 사다리수(answer)가 현재 탐색 중인 개수(total)이하라면, 굳이 더 탐색 하지 않고 종료하는 것이 효율성을 높일 수 있는 핵심이다. 또한 n이 여기서 열이고, h가 행이라서 보통 n이 행이고 m이 열인 문제가 많기에 헷갈릴 수 있음에 조심해야함. n,m,h = map(..

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제풀이 핵심 1. 사이클을 만족하는 조건은 점이 같은 색이고 4개이상으로 이루어져있으며, 처음 시작한 점에서 돌아온 점이 일치하는지 여부 2. 파고 들어가서 검사하고 또 검사하는 dfs 문제 나는 여기서 잘 생각을 못했던 부분은, 사이클 만족 조건을 제대로 지키지 않았다는 것.. 사이클인지 어떻게 확인하지? (매개변수로 count + 1씩해서 4개인지 확인 하면 되지), 돌아와서 같은 점인지 어떻게 확인할까?( 상하좌우 좌표 이동하면서 출발 좌표랑 같은..

def DFS(L,sum): global cnt if sum > T: return if L == k: if sum == T: cnt += 1 else: for i in range(cn[L] + 1): DFS(L+1, sum + (cv[L] * i)) if __name__ == "__main__": T = int(input()) k = int(input()) cv = list() cn = list() for i in range(k): a, b = map(int,input().split()) cv.append(a) cn.append(b) cnt = 0 DFS(0,0) print(cnt) # T 원을 거스름 돈으로 주려고 한다. 동전 종류가 k개이고, 각 동전 금액 cv 와 각 동전 개수 cn 배열에 입력을 ..

def DFS(L,sum): global res if L == n: if 0 < sum

def DFS(L,sum): global res if L > n: if res < sum: res = sum else: DFS(L + Ti[L], sum + Pi[L]) DFS(L+1,sum) if __name__ == "__main__": res = 0 n = int(input()) Ti = [0] Pi = [0] for _ in range(n): t, p = map(int,input().split()) Ti.append(t) Pi.append(p) DFS(1,0) print(res) # 최대 점수구하기 문제처럼, 어떤날에 상담을 하느냐 안하느냐가 포인트이다. 만약 1일째 상담을 하면 5일째부터 # 상담을 할 수 있고 만약 5일째 상담을 안한다면 6일째 상담으로 넘어가는 것이다. 역시 이 문제도 부분집..

def DFS(L,sum): global max result = 0 if sum > m: for i in range(L - 1): result += a[index[i]][0] if max < result: max = result elif sum == m: for i in range(L): result += a[index[i]][0] if max < result: max = result else: for i in range(n): if a[i][1] not in res: index[L] = i res[L] = a[i][1] DFS(L+1,sum + a[i][1]) if __name__ == "__main__": n, m = map(int,input().split()) res = [0] * n index =..

def DFS(v): global cnt if v == n: cnt += 1 for k in path: print(k, end= ' ') print() else: for i in range(1,n+1): if ch[i] == 0 and g[v][i] == 1: ch[i] = 1 path.append(i) DFS(i) ch[i] = 0 path.pop() if __name__ == "__main__": n, m = map(int,input().split()) # 1 부터 n 까지 연결 여부, 방문 여부를 위한 배열 g 와 ch g = [[0] * (n + 1) for _ in range(n + 1)] ch = [0] * (n + 1) # 항상 1부터 방문시작을 하므로 1로 체크한다. ch[1] = 1 cn..

import itertools as it n, f = map(int,input().split()) b = [1] * n cnt = 0 for i in range(1,n): b[i] = b[i-1] * (n - i)//i a = list(range(1, n + 1)) for tmp in it.permutations(a): sum = 0 for L, x in enumerate(tmp): sum += (x * b[L]) if sum == f: for x in tmp: print(x, end=' ') break # 파스칼 삼각형의 합으로 수열 추측하기 문제이다. 전과 다르게, 라이브러리를 이용해서 풀면 위와 같다. # 파이썬은 수열을 자동으로 만들어주는 라이브러리를 제공해 주는데, 라이브러리에 너무 의존하면 안..

def DFS(L,s): global cnt, res if L == k: if sum(res) % m == 0: cnt += 1 else: for i in range(s, n): res[L] = arr[i] DFS(L+1,i+1) if __name__ == "__main__": n, k = map(int,input().split()) arr = list(map(int,input().split())) m = int(input()) res = [0] * k cnt = 0 DFS(0,0) print(cnt) # n개의 수에서 k개를 뽑았을 때 그 합이 m의 배수인 경우의 개수를 구하자. # 나의 풀이: 조합구하기에서 해당 조합의 sum이 sum % m == 0 가 되는지 확인만 하면 된다. # 따라서 조합을 ..

def DFS(L): global cnt, res count = 0 for i in res: if i > 0 : count += 1 if count n: return if count == m: for k in range(1,n+1): if res[k] > 0: print(k, end=' ') cnt += 1 print() else: res[L] = 1 DFS(L+1) res[L] = 0 DFS(L+1) if __name__ == "__main__": n, m = map(int,input().split()) res = [0] * (n+1) cnt = 0 DFS(1) print(cnt) # 나의 풀이: 어떻게 문제를 풀지는 부분집합 구하기에서 응용을 하면 된다. 하지만 종료조건을 하나 ..