Jun Builds

1. 문제 설명https://www.acmicpc.net/problem/19042. 코드import sys input = sys.stdin.readline MOD = 15746 n = int(input()) if n == 1: print(1) elif n == 2: print(2) else: a,b = 1,2 for _ in range(3,n+1): a,b = b,(a+b) % MOD print(b)3. 풀이 과정n이 1일 때를 a로, 2일 때를 b로 한다.문제 속에 00 타일로 조건을 부여하였기 때문에a+b는 앞에 1을 붙이는 모든 경우와 앞에 00을 붙이는 모든 경우가 서로 겹치지 않게전체를 정확히 분할하기 때문에 가능한 모든 이진 수열의 개수가 된..

1. 문제 설명https://www.acmicpc.net/problem/91842. 코드import sys input = sys.stdin.readline dp = [[[0] * 21 for _ in range(21)] for _ in range(21)] vis = [[[False] * 21 for _ in range(21)] for _ in range(21)] def w(a: int, b: int, c: int) -> int: # base if a return 1 # clamp if a > 20 or b > 20 or c > 20: return w(20, 20, 20) if vis[a][b][c]: return dp[a][b..

1. 문제 설명https://www.acmicpc.net/problem/24416 2. 코드import sys input = sys.stdin.readline n = int(input().strip()) f = [0] * (n+1) f[1] = f[2] = 1 for i in range(3,n+1): f[i] = f[i-1] + f[i-2] cnt1 = f[n] cnt2 = n - 2 print(cnt1, cnt2)3. 풀이 과정cnt1은 재귀 fib의 실행 횟수이고, cnt2는 동적 프로그래밍(DP)의 실행 횟수이다.DP는 배열 f에 저장된 값을 꺼내어 쓰기 때문에 n이 1,2일 때를 제외한 n-2번으로 고정된다.재귀 횟수는 fib 값 자체이기 때문에 f[n]으로 고정된다.4. 자투리 개념동적 ..

1. 문제 설명https://www.acmicpc.net/problem/148892. 코드import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input().strip()) S = [list(map(int,input().split())) for _ in range(N)] pair = [[0]*N for _ in range(N)] for i in range(N): for j in range(i+1,N): pair[i][j] = S[i][j] + S[j][i] min_diff = float('inf') selected = [False] * N def calc(team): total = 0 m ..

1. 문제 설명https://www.acmicpc.net/problem/148882. 코드import sys input = sys.stdin.readline N = int(input().strip()) nums = list(map(int,input().split())) plus,minus,mul,div = map(int,input().split()) max_value = -10**9 - 1 min_value = 10**9 + 1 def my_div(a,b): if a >= 0: return a//b else: return -(-a//b) def dfs(idx, value, p, m, mu, d): global max_value, min_value ..

1. 문제 설명https://www.acmicpc.net/problem/25802. 코드import sys sys.setrecursionlimit(10000) # ----- 입력 ----- nums = list(map(int, sys.stdin.read().split())) board = [nums[i*9:(i+1)*9] for i in range(9)] # ----- 사용 여부 테이블 ----- row_used = [[False]*10 for _ in range(9)] col_used = [[False]*10 for _ in range(9)] box_used = [[False]*10 for _ in range(9)] def box_id(r, c): return (r//3)*3 + (c//3) f..

1. 문제 설명https://www.acmicpc.net/problem/96632. 코드import sys input = sys.stdin.readline N = int(input().strip()) cols = [False] * N # 사용 중인 열 diag1 = [False] * (2*N - 1) # r + c diag2 = [False] * (2*N - 1) # r - c + (N-1) def dfs(r: int) -> int: if r == N: return 1 cnt = 0 for c in range(N): d1 = r + c d2 = r - c + (N - 1) if cols[c] or d..

1. 문제 설명2. 코드import sys input = sys.stdin.readline N,M = map(int,input().split()) path = [] out = [] def dfs(start): if len(path) == M: out.append(" ".join(map(str,path))) return for x in range(start,N+1): path.append(x) dfs(x) path.pop() dfs(1) sys.stdout.write("\n".join(out))3. 풀이 과정N과 M (2)에 포인트가 하나만 추가된 문제이다.https://litd.tistory.com/666 [백준][20..

1. 문제 설명2. 코드import sys input = sys.stdin.readline N,M = map(int,input().split()) path = [] out = [] def dfs(): if len(path) == M: out.append(" ".join(map(str,path))) return for x in range(1,N+1): path.append(x) dfs() path.pop() dfs() sys.stdout.write("\n".join(out))3. 풀이 과정N과 M (2)에서 한 가지 포인트만 변화한 문제이다.https://litd.tistory.com/666 [백준][20단계 백트래킹] ..

1. 문제 설명https://www.acmicpc.net/problem/156502. 코드import sys input = sys.stdin.readline N,M = map(int,input().split()) path = [] out = [] def dfs(start: int): if len(path) == M: out.append(" ".join(map(str,path))) return for x in range(start,N+1): path.append(x) dfs(x+1) path.pop() dfs(1) sys.stdout.write("\n".join(out))3. 풀이 과정N과 M (1)에서 한 가지 포인트만..