문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 설계 - 이분탐색 - 처음에는 2중 while문을 이용하여 전선의 개수를 카운트, 시간초과 - cnt += line // mid 를 이용하여 while문 대신 한번에 cnt 계산 - start = 1로 해야 cnt += line // mid 에서 mid가 0이 되지 않는다. # 랜선 자르기 K, N = map(int, input().split()) arr = [i..
문제 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 설계 - 이분탐색 - 처음 주머니에 금액을 충전하고 카운트 + 1 - 모자라면 남은 금액을 통장에 집어넣고 K원 인출하는 조건 - answer는 K 가 end에서만 최신화 N, M = map(int, input().split()) arr = [int(input()) for _ in range(N)] start, end = 1, sum(arr) # end : 한번의 충전으로 모두 사용할 수 있는 최..
문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 설계 - 이분탐색 - 백준 문제 설명에 띄어쓰기가 헷갈리게 되어있어 문제를 이해하는데 오래 걸렸다. - SumV에 남아있는 것을 하나의 묶음으로 처리하는 것이 Point N, M = map(int, input().split()) arr = list(map(int, input().split())) # start : 블루레이 중 가장 큰값이 최소값이어야 모두 담을 수 있다. start, end = ma..
문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 설계 - 이분탐색 - 백준 [2805. 나무자르기] 문제와 연결하니 좀 더 쉽게 접근할 수 있었다. N = int(input()) arr = list(map(int, input().split())) M = int(input()) start, end = 1, max(arr) switch = 1 while switch: mid = (start + end) // 2 sumV = 0 for i..
문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 설계 - 처음에는 내음대로 풀었으나 시간초과 - 투포인터 학습 후 접근 - start와 end 설정이 중요하다. N, M = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() start = 1 end = max(arr) while start mid: # 높이보다 큰 나무..
문제 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 설계 - 처음에는 2중 for문을 이용하여 확인했으나 시간초과로 실패 - sort를 활용하여 접두어를 i와 i+1만 검사하면 된다. T = int(input()) for tc in range(T): result = 'YES' n = int(input()) arr = [input() for _ in range(n)] arr.sort() for i in range(n-1)..
문제 https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 설계 - 재귀, 피보나치 응용 n = int(input()) result = 0 def cal(level): global result if level == n: return result += level cal(level+1) cal(0) print(result)
문제 https://www.acmicpc.net/problem/14494 14494번: 다이나믹이 뭐예요? (1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다. www.acmicpc.net 설계 - DP 문제 - 피보나치와 동일한 개념 적용, 2중 for문 - 직접 그림을 그려 규칙을 찾아냈다. x, y = map(int, input().split()) arr = [[1]*(y+1) for _ in range(x+1)] for i in range(2, x+1): for j in range(2, y+1): arr[i][j] = arr[i-1][j] + arr[i][j-1] + a..
문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 설계 - bfs while문 안에서 pop(0)을 해야하는데 pop()으로 잘못 적어 오류를 찾는데 꽤나 고생했다. q에 append 하기 전에 visit 체크를 하면 시간이 덜 걸린다고 하니 참고하자. def bfs(x, y, cnt): global maxV q = [] q.append((x, y, 0)) visit = [[0] * b for _ in range(a)] visit[x][y] =..
문제 https://www.acmicpc.net/problem/19949 19949번: 영재의 시험 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행 www.acmicpc.net 설계 - DFS, 백트래킹 - level(수준): 10 / branch: 5 백트래킹을 적용했으나 파이썬으로 제출했을 경우 시간초과에 걸렸다. pypy 로 제출하여 통과했으나 메모리나 시간이 많이 소요되어 시간복잡도를 좀 더 줄여야 하는 코드라고 생각한다. def dfs(level): global cnt if level == 10: score = 0 for i in range(10): # 10문제..
