본문 바로가기
반응형

전체 글288

[BOJ][Python]15663번 풀이 https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys ssr = sys.stdin.readline def sol(): if len(ans) == m: print(*ans) return last = 0 for i in range(n): if visited[i] == 0 and last != num[i]: visited[i] = 1 ans.append(num[i]) last = num[i] sol() ans.pop() visited.. 2022. 7. 23.
[BOJ][Python]11725번 풀이 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline sys.setrecursionlimit(10**7) def dfs(parent): if visited[parent] == 1: return visited[parent] = 1 for i in adjacency_list[parent]: if visited[i] == 0: ans[i] = parent dfs(i) def bfs(): tmp = so.. 2022. 7. 22.
[BOJ][Python]10994번 풀이 https://www.acmicpc.net/problem/10994 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net n = int(input()) line_len = 4*(n-1)+1 cnt = 1 stars = [['*' for _ in range(line_len)] for _ in range(line_len)] while line_len - 2*cnt >= 1: for i in range(cnt, line_len-cnt): for j in range(cnt, line_len-cnt): if cnt%2 == 1: stars[i][j] = ' ' else: stars[i][j] = '*' cnt += 1 for i in stars: prin.. 2022. 7. 21.
[BOJ][Python]11053번 풀이 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net n = int(input()) a = list(map(int, input().split())) dp = [1 for _ in range(n)] for i in range(n): for j in range(i+1,n): if a[j] > a[i]: dp[j] = max(dp[j], dp[i]+1) print(max(dp).. 2022. 7. 21.
[BOJ][Python]10157번 풀이 https://www.acmicpc.net/problem/10157 10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net c,r = map(int, input().split()) k = int(input()) s = 0 shell = [0] while 1: a = ((c-1-2*s)+(r-1-2*s))*2 if a > 0: shell.append(a + shell[-1]) s += 1 else: break if c*r < k : print(0) else: r_start = 0 c_start = 0 f.. 2022. 7. 20.
[BOJ][Python]15657번 풀이 https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net import sys ssr = sys.stdin.readline def sol(idx): if len(ans) == m: print(*ans) return for i in range(idx,n): ans.append(num[i]) sol(i) ans.pop() return n,m = map(int, ssr().split()) num = list(map(int, ssr().split())).. 2022. 7. 20.
[BOJ][Python]15654번 풀이 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net import sys ssr = sys.stdin.readline def sol(num_len): if num_len == m: print(*ans) return for i in range(n): if visited[i] == 1: continue visited[i] = 1 ans.append(num[i]) sol(num_len + 1) ans.pop() visited[i] = 0 retu.. 2022. 7. 19.
[BOJ][Python]12928번 풀이 https://www.acmicpc.net/problem/12928 12928번: 트리와 경로의 길이 첫째 줄에 N과 S가 주어진다. (1 ≤ N ≤ 50, 1 ≤ S ≤ 1,000) www.acmicpc.net def sol(n,c):# n = 남은 노드 갯수, c = 현재까지 만들어진 2짜리 단일경로 갯수, 노드 2개짜리 트리에서 시작(2짜리 단일경로라 0개) if n == 0 and c == s:#모든 노드를 다 붙였을 때 단일 경로 갯수가 주어진 s와 같을 때 print(1)# 가능하다 exit()#프로세스 종료 if n == 0 or t[n][c] or c > s: #n이 0이거나 t[n][c]가 True거나, c가 s보다 클 때 return#리턴 t[n][c] = 1 for i in range.. 2022. 7. 19.
[BOJ][Python]11203번 풀이 https://www.acmicpc.net/problem/11203 11203번: Numbers On a Tree The only line of input contains the height of the tree H, 1 ≤ H ≤ 30 and a string consisting of the letters ‘L’ and ‘R’, denoting a path in the tree starting in the root. The letter ‘L’ denotes choosing the left child, and the letter ‘R www.acmicpc.net line = input().strip() if line.isdigit(): print(2**(int(line)+1)-1) else: h, orde.. 2022. 7. 18.
[BOJ][Python]2407번 풀이 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()) t = [0 for _ in range(101)] t[1] = 1 for i in range(2, 101): t[i] = i*t[i-1] print(t[n]//t[n-m]//t[m]) 아주 간단한 문제라 풀이가 필요없을지도 모르겠습니다만, 오랜만에 조합 공식도 떠올릴 겸 dp로 풀면 시간도 짧게 걸린다는 사실도 상기시킬 겸 작성해봤습니다. 큰 의미없이 포스팅 수만 늘어나는 일인지도 모르겠지만요. 2022. 7. 18.
반응형

티스토리툴바