문제 https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 설계 - dfs를 들어가며 11명의 선수를 확인한다. - 자리가 배치된 선수 번호를 visit 배열에 추가 및 삭제하며 한 번호당 한명씩만 들어가게 한다. 파이썬 def dfs(sumV, level): global maxV, visit if level == 11: if maxV < sumV: maxV = sumV return for i in range(11): if arr[level][i] and i not in vis..
문제 https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 설계 - 주어지는 입력값은 모두 같은 길이로 주어진다. 파이썬 N = int(input()) arr = [input() for _ in range(N)] answer = '' for i in range(len(arr[0])): now = arr[0][i] flag = 0 # 하나라도 일치하지 않을 경우 표시 for j in range(1, N): if now != arr[j][i]: f..
문제 https://www.acmicpc.net/problem/1283 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 설계 - 1. 띄어쓰기를 기준으로 나눠진 단어의 첫번째 이니셜만 확인한다. - 1번 조건을 만족하지 못했을 경우 각 단어의 문자를 하나씩 확인한다. 파이썬 bucket = [0] * 100 N = int(input()) for _ in range(N): arr = list(map(str, input().split())) shortcut = 0 # 단축키가 지정되어있는지 확인 #..
문제 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 설계 - vip 사이의 구간별 자리수를 cal 함수에 넣는다. - cal 함수로 구간별 경우의 수를 구한 뒤 answer에 곱한다. 파이썬 # 앉을 수 있는 경우의 수를 계산하는 점화식 함수 def cal(n): if n == 1: return 1 elif n == 2: return 2 elif n == 3: return 3 else: dp = [0] * (n + 4) dp[0], dp[1] = 1, 1..
문제 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 설계 파이썬 N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] arr.sort() # 가장 높은 기둥의 크기와 index 찾기 maxI, maxV = 0, 0 for i in range(N): if maxV < arr[i][1]: maxV = arr[i][1] maxI = i # 앞에서부터 가..
문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 설계 파이썬 N, K = map(int, input().split()) arr = [i + 1 for i in range(N)] answer = [] now = K - 1 while len(arr): answer.append(arr[now]) arr.pop(now) now = now + K - 1 # pop을 먼저 했으므로 숫자 1개가 줄어든다. if len(arr) > 0: # zero division 방지 now %= len(arr) # 결과 출력 print('', sep='')
문제 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 설계 - 소수 : 1과 자기 자신으로만 나누어지는 수 - 2 ~ n-1 까지 모든 수로 나누어 판별 가능하지만 비효율적이다. - 에라토스테네스의 체 : 제곱근까지만(가운데 약수까지만) 확인하면 된다 M = int(input()) N = int(input()) bucket = [] for i in range(M, N + 1): if i == 1: # 예외처리 중요! 1일 경우 소수가 될 수 없다. con..
문제 https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 설계 - 반대로 접근하여, 주어진 배열을 모두 0으로 만드는 최소 횟수를 계산한다. N = int(input()) arr = list(map(int, input().split())) cnt = 0 while sum(arr) > 0: # arr이 모두 0이 될때까지 반복 check = 0 for i in range(N): # 전부 짝수인지 check if arr[i] % 2 =..
문제 https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 설계 - 3개씩 묶어서 확인 하면서 1,3번째의 합이 가장 작은 경우의 수를 저장, 2번째 index를 제거한다. - 위 과정을 반복하면서 리스트에 2개가 남을때 까지 반복한다. - 전체 합계의 최대값을 구해야 함으로 dfs를 사용, while문으로 사용시 반례가 존재한다. ※ while문 사용시 반례 8 10 7 8 9 10 2 4 13 정답 : 612 def dfs(arr, sumV..
문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 설계 - DP - 주어진 수의 3가지 경우의 수를 묶어 더하면 해당 수의 경우의 수를 나타낸다. # 1 2 3 4 5... (number) # 1 2 4 7 13... (total) # 1 + 2 + 4 = 7 # 2 + 4 + 7 = 13 N = int(input()) arr = [int(input()) for _ in range(N)] for i in range(N): number = [1, 2, 4] if arr[i]
