태브로의 개발위키

출처 :https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 : n = int(input()) a = [0]* (n+1) for i in range(2,n+1): a[i] = a[i-1] + 1 if i % 3 == 0 : a[i] = min(a[i], a[i//3]+1) if i % 2 == 0 : a[i] = min(a[i], a[i//2]+1) print(a[n]) 다이나믹 프로그래밍의 정석인 문제가 아닐까 생각한다. 하지만 못 풀었다... 조금 이런 접근이 낯설었다. 우선 다이나믹 프로그램에서는 무엇을 미리 배열을 정할지를 생각해야한다. 지금까지 문제..

출처 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 : t = int(input()) sol = [0] * 101 sol[1], sol[2], sol[3] = 1, 1, 1 for _ in range(t): n = int(input()) for i in range(4,n+1): sol[i] = sol[i-3] + sol[i-2] print(sol[n])

출처 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) a = [0]*1000001 a[1],a[2] = 1, 2 for i in range(3,n+1): a[i] = (a[i-2]+a[i-1])%15746 print(a[n]) 풀이 : 그래서 피보나치 문제임을 확인했고 이게 재귀함수를 사용해서 풀었었는데 그렇게 풀면 메모리초과가 나기 때문에 위 풀이..

출처 : https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 풀이 : dp = [[[0]*(21) for _ in range(21)] for _ in range(21)] def w(a,b,c): if a 20 : return w(20,20,20) if dp[a][b][c]: # 0 이면 반환을 안함 return dp[a][b][c] if a < b < c : dp[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)..

출처 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 : t = int(input()) zero = [1,0,1] one = [0,1,1] def fibo(num): length = len(zero) if num >= length: for i in range(length, num+1): zero.append(zero[i-2]+zero[i-1]) one.append(one[i-2]+one[i-1]) print(f'{zero[num]} {one[num]}') for _ in range(t): fibo(int(input())) 문제 부터..

출처 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이: n = int(input()) ans = 0 row = [0]* n def right(x): for i in range(x): if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i) : return False return True def queen(x): global ans # 함수 안에서 ans 값이 변할 수 있도록 해줌 if x == n: ans..

출처 : https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 n = int(input()) mat = [] A = [] B = [] for _ in range(n): mat.append(list(map(int, input().split()))) ans = float('Inf') def dfs(depth): global ans if depth == n//2: A_sum = 0 B_sum = 0 for i in range(n): if i not in A: B.appe..

출처 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이: n = int(input()) a = list(map(int, input().split())) ysj = list(map(int, input().split())) maximum = -1e9 minimum = 1e9 def dfs(depth, tot, plus, minus, multiply, divide): global maxi..

출처 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net a, b = map(int, input().split()) ans = [] def bts(start): if len(ans) == b : print(' '.join(map(str,ans))) return for i in range(start, a+1): ans.append(i) bts(i) ans.pop() start += 1 bts(1) 풀이: 이전과 똑같이 하면되는데 다만 함수에 변..

출처 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 a ,b = map(int, input().split()) ans = [] def bts(): if len(ans) == b: print(' '.join(map(str,ans))) return for i in range(1, a+1): ans.append(i) bts() ans.pop() bts() 첫 백트래킹 문제를 해결할 때 열심히 이해해서 몇 일이 지나도 코드를 쉽게 구현하고..