본문 바로가기
반응형

전체 글573

파스칼 삼각형(조합) nCr = n-1Cr-1 + n-1Cr n, r = map(int, input().split()) dp = [[1]*(i+1) for i in range(n+1)] for i in range(2, n+1): for j in range(1, i): dp[i][j] = dp[i-1][j-1]+dp[i-1][j] print(dp[n][r]) # nCr 2021. 9. 2.
[수학] 백준 2407번: 조합 / 실버 2 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net n, m = map(int, input().split()) dp = [[1]*(i+1) for i in range(n+1)] for i in range(2, n+1): for j in range(1, i): dp[i][j] = dp[i-1][j-1]+dp[i-1][j] print(dp[n][m]) 파스칼 삼각형의 원리를 이용하여 dp로 풀었다. nCr = n-1Cr-1 + n-1Cr 정답자 코드를 보니 그냥 팩토리얼로도 풀린다. 2021. 9. 2.
[DFS, BFS] 백준 1167번: 트리의 지름 / 골드 3 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net import collections n = int(input()) graph = collections.defaultdict(list) for i in range(n): row = list(map(int, input().split())) start = row[0] for j in range(1, len(row)-1, 2): next, w = row[j], row[j+1] graph[s.. 2021. 9. 1.
[구현] 삼성 기출/ 백준 20056번: 마법사 상어와 파이어볼 / 골드 5 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net import collections import sys input = sys.stdin.readline n, m, k = map(int, input().split()) table = [[collections.deque() for _ in range(n)] for _ in range(n)] answer = 0 for i in range(m): r, c, m, s.. 2021. 8. 25.
[구현] 백준 20055번: 컨베이어 벨트 위의 로봇 / 실버 1 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 삼성 기출이라그런지 좀 까다로웠다. import sys input = sys.stdin.readline n, k = map(int, input().split()) nums = list(map(int, input().split())) up = 0 down = n-1 count = 0 zero = 0 robots = [False for _ in range(2*n)] while T.. 2021. 8. 24.
[DFS, BFS] 백준 9466번 : 텀 프로젝트 / 골드 3 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net import sys input = sys.stdin.readline tc = int(input()) for _ in range(tc): n = int(input()) lst = list(map(int, input().split())) visited = [False for _ in range(n)] cycle = [False for _ in range(n)] for i in range(n): if vis.. 2021. 8. 24.
반응형