백준(12)
-
[백준] 1463 | 1로 만들기 | C++
풀이의 핵심은 다이나믹 프로그래밍이다. 0. dp[i]의 값은 'i를 1로 만들기 위한 최소 연산 횟수'를 의미한다. 1. 2부터 n까지 i반복: dp[i]는 dp[i-1]에 1을 더한 값으로 초기화. 만약 i가 2의 배수라면: dp[i]=min(dp[i], dp[i/2]+1)로 초기화한다. 만약 i가 3의 배수라면: dp[i]=min(dp[i], dp[i/3]+1)로 초기화한다. 2. dp[n]을 출력한다. 0. dp를 벡터로 선언하면, OutofBounds에 안걸린다. 1. i가 6의 배수라면 2로도, 3으로도 나눠 떨어진다. 3으로 나누었을 때의 횟수가 더 적으므로 2부터 처리하도록 한다. 정답 소스코드 #include using namespace std; int n; int main() { ios..
2022.09.03 -
[백준] 16198 | 에너지 모으기 | C++
풀이의 핵심은 이렇다. 0. 입력받은 에너지값들(배열 inp)을 마음껏 조작할 수 있도록 객체 하나를 복사생성해둔다(배열 cpy). 1. DFS는 처리해야 할 구슬의 순서(배열 ord)를 작성한다. 2. 순서구성이 완료되면: 계산할 에너지합 변수 선언(tmp = 0) 구슬처리(cpy조작) 위한 순서탐색(for ord): 해당순서(ord[i])의 에너지값을 사용했단 의미에서 0을 대입(cpy[ord[i]]=0) 해당순서의 이전순서(ord[i]-1)를 l, 다음순서(ord[i]+1)를 r로 선언 사용되지 않은(0이 아닌) 구슬을 찾기 위해 l, r 세팅 세팅완료된 l, r을 이용하여 tmp에 에너지 모은다. 모아둔 tmp가 res보다 크다면 res 갱신 3. 최댓값 res를 출력 0. 구슬을 사용하면 그 구..
2022.09.03 -
[백준] 숨바꼭질 | 1697 | C++
풀이의 핵심은 BFS이다. 필자는 배열 안에 걸린시간을 저장하는 방식으로 풀었다. 정답 소스코드 #include using namespace std; int n, k; int arr[100004]; queue Q; void BFS() { while(!Q.empty()) { int x=Q.front(); Q.pop(); if(x==k) return; if(x-1>=0 && x-1=0 && x+1=0 && x*2>n>>k; arr[n]=1; Q.push(n); BFS(); cout
2022.08.20 -
[백준] 12865 | 평범한 배낭 | C++
풀이의 출처: https://chanhuiseok.github.io/posts/improve-6/ 이 문제는 냅색 알고리즘(knapsack algorithm)이 무엇인지 알 수 있게 해주는 문제이다. 풀이의 핵심은 2가지로 나눠서 볼 수 있다. 1. 이차원 다이나믹 테이블 풀이 준비물이 있다. i번째 물건의 무게를 저장하는 배열 W, i번째 물건의 가치를 저장하는 배열 V, i번째 물건까지 고려할 때 j용량까지 담을수 있는 최대가치값 dp[][] dp[i][j]의 의미는 i번째 물건까지 고려할 때, j용량에 담을 수 있는 가치값의 최대합이다. 따라서 다음과 같이 2중 for문을 작성하려 한다. 1번째 물건부터 n번째 물건까지 i반복: 1용량부터 k용량까지 j반복: j번째 용량에 i물건 투입가능: dp[i..
2022.08.17 -
[백준] 14501 | 퇴사 | C++
재귀와 동적계획법으로 풀 수 있다. 1. 재귀(브루트포스) 재귀함수의 변수로는 날짜(인덱스) - int L, 누적상담료 - int psum 으로 설정하였다. 현재 날짜를 L이라고 하자. 날짜 L에 상담을 할 것인지 하지 않을 것인지 선택을 해야 한다. 1. 날짜 L에 상담하기로 선택했다면, 다음에 선택할 수 있는 날짜는 언제인가? 바로 날짜 L+T[L]부터 상담이 가능할 수 있지 않은가? 그리고 여태껏 누적되어온 상담료 psum에 오늘 선택한 상담료 P[L]을 더한다. void f(int L, int psum) { ... f(L+T[L], psum+P[L]); } 다만 조건이 있다. 상담을 진행하는 도중에 휴가날을 맞이할 수는 없는 노릇이다. 그래서 상담할지 선택하기 전에, 다음 상담이 가능한 날짜(L+..
2022.07.21 -
[백준] 17478 | 재귀함수가 뭔가요? | C++
풀이의 핵심은 이렇다. 정답 소스코드 #include using namespace std; int n; void f(int L) { for(int i=0; i
2022.07.20