BOJ (77) 썸네일형 리스트형 BOJ : 18310 안테나 (파이썬) 문제 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 이 문제는 정렬로 간단하게 풀 수 있는 문제다. 집들을 리스트로 입력을 받고 그 리스트를 len() 함수를 통해 길이를 구한 후 -1을 해준 후 2를 나눈몫을 가진 인덱스를 가진 값이 정답이다. 소스코드 import sys n = int(sys.stdin.readline()) house = list(map(int, sys.stdin.readline().split())) house.sort() le = (len(ho.. BOJ : 1835 병사배치하기 (파이썬) 문제 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍으로 풀 수 있다. 이중 for 문을 이용해 첫번째 for문으로는 비교해야할 요소를 하나 정하고 두번째 for문으로 비교해야할 요소들의 전을 한번씩 탐색해주면서 +1 해줘서 d를 채워 나가는 식으로 풀 수 있다. 소스코드 import sys n = int(sys.stdin.readline()) d = [1] * (n+1) lst = list(map(in.. BOJ : 14501 퇴사 (파이썬) 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 기법으로 풀 수 있는 문제이다. 중요한 점은 for문을 1부터 시작했으면 d[n]에 해당하는 값들이 다 0 으로 되어있기 때문에 그 당일날 보상만 계산이 되기 때문에 뒤에서부터 for문을 돌렸다. import sys n = int(sys.stdin.readline()) d=[0] * (n+1) #t는 시간 p는 보상 lstt = [] lstp = [] for _ in range(n) : t,p = map(int, sys.stdin.readline().split()) lstt.append(t) lst.. BOJ : 2470 두용액 (파이썬) 문제 https://www.acmicpc.net/problem/2470 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 이분탐색을 통해서 풀 수 있는 문제다. 만약 이분탐색을 하지않게 되면 ' N은 2 이상 100,000 이하이다.' 라는 조건의 의해 최악의 경우 (100,000 - 1)! 만큼의 연산을 해야하기 때문에 엄청난 시간이 소요 될것이다. (제 뇌피셜입니다..) 다른 문제들은 범위를 지정해놓고 중앙값을 이용해 이분탐색을 하는 문제들을 대부분 많이 접했었는데, 이번 문제는 접근방식이 조금 달랐다. start 범위를 리스트에 제일 앞 인덱스 번호, end 범위를 리스트에 제일 뒷 인덱스 번호를 지정해줬다... BOJ : 1463 1로 만들기 (파이썬) 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그램을 이용해서 푸는 문제이다. 문제에서 주어진 조건은 총 3가지인데, 모든 연산을 해가면서 min() 이라는 내장함수를 이용해서 해당하는 숫자 x일때의 최솟값을 저장해주면 답을 구할 수 있다. import sys x = int(sys.stdin.readline()) d = [0] * (x+1) for i in range(2,x+1) : #현재 수에서 1 뺄때 d[i] = d[i-1] + 1 #2로 나눠떨어질때 if i % 2 == 0 : d[i] = min(d[i // 2] + 1, d[i].. 이전 1 ··· 7 8 9 10 다음
