알고리즘/BOJ32 [BOJ] 12852. 1로 만들기 2 문제https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.www.acmicpc.net 주요 아이디어앞에서 풀었던 '1로 만들기' 문제의 로직을 그대로 가져다 쓰려고 했다. 코드 구현 (Python 3)더보기 n = int(input())dp = [0] * (n+1)# dp[i] = i를 만들기 위해 필요한 최소 연산횟수for i in range(2, n+1): # 1을 빼기 dp[i] = dp[i-1] + 1 # 2로 나눠진 것 전에서 더하기 1 if i % 2 == 0: dp[i] = mi.. 2024. 4. 24. [BOJ] 1463. 1로 만들기 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 주요 아이디어 1~n까지의 dp list를 만들고, 해당 숫자를 만들기 위해 필요한 최소 연산 횟수를 구하면 된다. 코드 구현 (Python 3) 더보기 n = int(input()) dp_list = [0] * (n+1) # 1로 만들기니까 2 이상부터 시작 for i in range(2, n+1): # 기본적으로 할 수 있는 연산 = 이전 연산횟수에서 빼기 한번이므로 +1 dp_list[i] = dp_list[i-1] + 1 if i%2 == 0: # 이전 연산 (i*2) 에서 나누기 한번이므로 +1 .. 2024. 4. 21. [BOJ] 12865. 평범한 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 개인적으로 좀 어려웠던 문제.. 주요 아이디어 처음 생각했던 방법은, 가치 기준 내림차순 & 같은 가치일 경우 무게 기준 오름차순 한 다음 for문을 돌면서 하나씩 더해주며 최대값을 찾는 방법이었다. 코드 구현 (Python 3) 더보기 n, k = map(int, input().split()) items = [] for _ .. 2024. 4. 21. [BOJ] 1026. 보물 문제 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 주요 아이디어 전체 합을 최소값으로 만들려면, (현재 A배열의 최대값) * (현재 B배열의 최소값) 을 하나씩 더해주면 된다. 코드 구현 (Python 3) 간단하게 풀려면, A를 오름차순 / B를 내림차순 해서 곱한 후 하나씩 더해주면 된다. 더보기 n = int(input()) a = list(map(int, input().split())) b = list(map(int, inpu.. 2024. 4. 21. [BOJ] 14501. 퇴사 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 돈미새 백준이.. 주요 아이디어 풀 때마다 항상 느끼지만 DP 문제는 정말 아이디어가 중요한 것 같다.. 앞에서 (i=1) 부터 접근하지 말고, 맨 끝 날짜부터 접근해보자 매 상담에 대해 현재 상담일자의 이윤 + 현재 상담을 마친 일자로부터의 최대 이윤 계산 즉 dp[i] = i번째 날 ~ n번째 날까지 낼 수 있는 최대 이익이다 예제 살펴보기 더보기 7일차에는 상담이 불가하다 상담 소요 일자 + 현재 일자 = 2 + 7 > n 이기 때문이다 dp[7] = 0, max_value = 0 6일차에도 상담이 불가능하다 상담 소요 일.. 2024. 4. 6. [BOJ] 14502. 연구소 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 주요 아이디어 굉장히 기초적인 BFS 문제이다. 기본적인 아이디어는 다음과 같다 빈 칸 중 벽을 세울 칸 3개의 좌표를 조합으로 뽑아낸다. 문제 조건 중 "무조건 3개의 벽"을 세우라고 했기 때문에 별다른 예외처리는 안해도 된다 조합 순회를 돌면서 벽을 세우고, 해당 벽을 세웠을 때 바이러스가 전파된 경우를 확인한다 바이러스 전파는 bfs 방식으로 체크한다 원본이 바뀌는 것을 막기 위해 bfs 진행 시마.. 2024. 4. 6. 이전 1 2 3 4 5 6 다음
