백준3 [C++] 백준 12865 - 평범한 배낭 백준 12865 : 평범한 배낭 난이도 : 골드 5 시간 : 해결 x 문제 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 풀이 과정 자력으로 풀어보려고 했지만 도저히 해결 방법이 나오질 않아 정답을 참고했다. 먼저 다음과 같은 dp[i][j] 배열을 정의한다. dp[i][j] = 처음부터 i번째까지의 물건을 살펴보고, 배낭의 용량이 j였을 때 배낭에 들어간 물건의 가치합의 최댓.. 2023. 3. 2. [C++] 백준 2565 - 전깃줄 백준 2565 : 전깃줄 난이도 : 골드 5 시간 : 28분 소요 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 과정 LIS(Longest Increasing Subsequence)에 대한 개념과 구현 방법에 대해서 알고 있으면 이 문제는 쉽게 풀 수 있다. 문제를 요약하면 교차하는 것을 제거하는 데, 제거 횟수를 최소로 하는 것이다. 먼저 교차에 대해 고민해볼 필요가 있다. 교차하지 않기 위해서는 의 n번째 위치에서 로 연결할 때 1~n.. 2023. 2. 24. [C++] 백준 11051 -이항 계수 2 난이도 : 실버2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 방법 이항계수의 특징을 생각하면 쉽게 풀 수 있는 문제이다. nCr = (n-1)Cr + (n-1)C(r-1) mod 연산이 어떻게 되야하는지는 고민을 했다. (a+b)%mod C = { (a%C) + (b%C) } % C 이 2가지의 공식을 이해했다면 코드 작성은 어렵지 않다. 하지만 시간 초과가 발생하였다. 이 방식이 재귀적이어서 이런 문제가 발생하는가 싶어 아예 코드를 갈아엎어야 하는지 혼란스러웠다. 그래도 속는셈 치고, 메모이제이션 방법.. 2023. 2. 24. 이전 1 다음
