지식을 나누는 공간

문제 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 코드 import sys input=sys.stdin.readline for _ in range(int(input())): a,b=map(int, input().split()) dis=b-a; n=0 while 1: if n*(n+1)>=dis: break n+=1 if n**20 and cur+icnt+1): dp[i][cur+i]=cnt+1 q..

문제 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 코드 import sys input=sys.stdin.readline #+51 def recur(a,b,c): if dp[a][b][c]!=-1: return dp[a][b][c] if a71: dp[a][b][c]=recur(71,71,71) elif a

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 코드 from collections import deque n,m=map(int, input().split()) graph=[list(map(int, list(input().rstrip()))) for _ in range(n)] visited=[[[0]*2 for _ in range(m)] for _ in range(n)] dx=[0,0,-1,1] dy=[1,-1,0..

문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 코드 import sys input=sys.stdin.readline n,k=map(int, input().split()) dp=[0]*(k+1) c=[] for _ in range(n): c.append(int(input())) dp[0]=1 for i in c: for j in range(1,k+1): if j-i>=0: dp[j]+=dp[j-i] print(dp[k]) 생각 정리 dp[0..

문제 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 코드 n=int(input()) def hanoi(n,start,end): if n==1: print(start, end) return hanoi(n-1,start,6-start-end) #1단계 print(start,end) #2단계 hanoi(n-1,6-start-end,end) #3단계 print(2**n-1) hanoi(n,1,3) 생각 정리

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 코드 from collections import deque import sys input=sys.stdin.readline def bfs(start): visited=[-1]*(v+1) queue=deque() queue.append(start) visited[start]=0 max_a=[0,0] #dis, node while queue: t=queue.popleft() fo..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 코드 import sys from collections import deque input=sys.stdin.readline queue=deque() m,n,h=map(int, input().split()) #n행 m열 dn=[0,0,-1,1,0,0] dm=[-1,1,0,0,0,0] dh=[0,0,0,0,-1,1] graph=[] for i in range(h): tem..

코드 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 코드 a,b,c=map(int,input().split()) def make(a,b): if b == 1: # b의 값이 1이면 a % C를 return한다. return a % c else: temp = make(a, b // 2) # a^(b // 2)를 미리 구한다. if b % 2 == 0: return temp * temp % c # b가 짝수인 경우 else: return temp * temp * a % c # b가 홀수인 경우 print(mak..

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 코드 n=int(input()) array=list(map(int, input().split())) answer=[-1]*n #stack에 index를 넣어줌 stack=[] stack.append(0) for i in range(1,len(array)): while stack and array[stack[-1]]

문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 코드 from sys import stdin input = stdin.readline def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(a, b): a = find(a) b = find(b) if a != b: parent[b] = a number[a] += number[b] ..