백준 1463 : 1로 만들기
문제
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[1000001];
int main(){
for(int i=2;i<1000001;i++){
//cout<<"i: "<<i<<"\n";
vector<int> v;
int divide_three=0;
int divide_two=0;
int minus_one=0;
if(i%3==0){
divide_three=arr[i/3];
v.push_back(divide_three);
}
if(i%2==0){
divide_two=arr[i/2];
v.push_back(divide_two);
}
minus_one=arr[i-1];
v.push_back(minus_one);
//cout<<"divide_two : "<<divide_two<<" divide_three : "<<divide_three<<" minus_one : "<<minus_one<<"\n";
auto result=min_element(v.begin(),v.end());
arr[i]=*result+1;
}
int N;
cin>>N;
cout<<arr[N];
}바킹독 코드
vector를 사용할 필요 없이
d[i] = d[i-1] + 1
을 해준 뒤,
if문 으로 처리하여 3으로 나눈 값과 d[i]로 비교하여 최솟값을 찾는 코드를 짜면
코드가 더 깔끔하다.
2로 나눈 값도 동일하게 처리해준다.
d[i]=d[i-1]+1;
if(i%3==0) min(d[i],d[i/3]+1);
if(i%2==0) min(d[i],d[i/2]+1);전체코드
#include <bits/stdc++.h>
using namespace std;
int d[1000005];
int n;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
d[1] = 0;
for(int i = 2; i <= n; i++){
d[i] = d[i-1]+1;
if(i%2 == 0) d[i] = min(d[i],d[i/2]+1);
if(i%3 == 0) d[i] = min(d[i],d[i/3]+1);
}
cout << d[n];
}백준 9095 : 1,2,3 더하기
문제
코드
#include <iostream>
using namespace std;
int arr[11];//1부터 10까지
int main(){
arr[1]=1;// 1
arr[2]=2;// 2 1+1
arr[3]=4;// 3
// 2+1 1+1+1
// 1+2
for(int i=4;i<=11;i++){
arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
}
int N;
cin>>N;
for(int i=0; i<N;i++){
int test_case=0;
cin>>test_case;
cout<<arr[test_case]<<"\n";
}
}백준 2579 : 계단 오르기
문제
트러블슈팅
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<pair<int,int>>> sum(300); // {score,cnt}
int arr[300];
void print_arr(int N){
for(int i=0;i<N;i++){
for(int j=0;j<sum[i].size();j++){
cout<<sum[i][j].first<<","<<sum[i][j].second<<" ";
}
cout<<"\n";
}
}
int main(){
int N;
cin>>N;
for(int i=0;i<N;i++){
cin>>arr[i];
}
for(int i=0;i<N;i++){
if(i==0){
sum[0].push_back({arr[0],0});
continue;
}
else if(i==1){
sum[1].push_back({arr[1],0});//2칸으로 올라옴
int score=sum[0][0].first;
int cnt=sum[0][0].second;
sum[1].push_back({score+arr[1],++cnt});//1칸 1칸 올라옴
continue;
}
//2이상일 때
//2칸 전에 있는 것들에 score 모두 arr[i]를 더하고 push하기,cnt는 0
for(int j=0;j<sum[i-2].size();j++){
sum[i].push_back({arr[i]+sum[i-2][j].first,0});
}
//1칸 전에 있는 것들에 score 모두 arr[i]를 더하고 push하기,cnt++ 더하기
//cnt가 2였다면 push하지 않기
for(int j=0;j<sum[i-1].size();j++){
if(sum[i-1][j].second==1)
continue;
sum[i].push_back({arr[i]+sum[i-1][j].first,sum[i-1][j].second+1});
}
//cout<<i<<"일때 : \n";
//print_arr(N);
}
int max_num=sum[N-1][0].first;
for(int j=1;j<sum[N-1].size();j++){
max_num=max(max_num,sum[N-1][j].first);
}
cout<<max_num;
//1계단은 10
//2계단은 10(1)+20(1)=30 20(2)
//3계단은 20(2)+15(1)=35 10(1)+15(2)=25
}기껏 열심히 풀었더니 시간초과가 떴다.
그렇겠지.. 시간복잡도가 O(N^2)니까 .. ^^
코드
#include <iostream>
using namespace std;
int D[301][3];
int arr[301];
int main(){
//D[][1]은 계단 1개 연속으로 밟은 것
//D[][2]는 계단 2개 연속으로 밟은 것
//D[k][1] = max(D[k-2][1] , D[k-2][2]) + arr[k];
//D[k][2] = D[k-1][1] + arr[k];
int N;
cin>>N;
for(int i=1;i<=N;i++)
cin>>arr[i];
D[1][1]=arr[1];
D[2][1]=arr[2];
D[2][2]=arr[1]+arr[2];
for(int k=3; k<=N; k++){
D[k][1] = max(D[k-2][1] , D[k-2][2]) + arr[k];
D[k][2] = D[k-1][1] + arr[k];
}
cout<<max(D[N][1],D[N][2]);
}메모리 초과가 안나는 구현방법은
k번째 계단일 때, 1번 연속으로 밟은 계단과 2번 연속으로 밟은 계단의 경우를 나누어서 구현하면 되었다.
D[k][1] = max(D[k-2][1] , D[k-2][2]) + arr[k];
D[k][2] = D[k-1][1] + arr[k];
사소한 실수
D[1][1]값과 D[2][1]값 , D[2][2]값을 10,20,30으로 해당 테스트케이스에만 맞게 할당해놓았다.
이러면 당연히 틀렸습니다가 뜨게 되어있는데 , 어디서 틀렸지?! 하며 찾아내지 못했다..
틀렸습니다가 떴을 때, 해당 테스트케이스만 맞게 하드코딩을 한 건 아닌지 다시 확인해보자.
정말 바보같은 실수
백준 1149 : RGB 거리
문제
코드
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1000][3];
int DP[1000][3];
int main(){
int N;
cin>>N;
for(int i=0;i<N;i++)
for(int j=0;j<3;j++)
cin>>arr[i][j];
DP[0][0]=arr[0][0];
DP[0][1]=arr[0][1];
DP[0][2]=arr[0][2];
for(int i=1;i<N;i++){
DP[i][0]=min(DP[i-1][1],DP[i-1][2])+arr[i][0];
DP[i][1]=min(DP[i-1][0],DP[i-1][2])+arr[i][1];
DP[i][2]=min(DP[i-1][0],DP[i-1][1])+arr[i][2];
}
int min_num=DP[N-1][0];
min_num=min(min_num,DP[N-1][1]);
min_num=min(min_num,DP[N-1][2]);
cout<<min_num;
}백준 11726 : 2*n 타일링
문제
코드
#include <iostream>
using namespace std;
int DP[1000];
int main(){
int n;
cin>>n;
DP[0]=1;
DP[1]=2;
for(int i=2;i<n;i++)
DP[i]=(DP[i-1]+DP[i-2])%10007;
cout<<DP[n-1];
}트러블슈팅
점화식을 i-1인 경우와 i-2인 경우를 더했을 때가 i일때의 개수였는데,
DP[i]=DP[i-1]+DP[i-2]
이전에는 점화식을
DP[i]=DP[i-1]+DP[i-2]*2
라고 세웠었다.
그런데 DP[i-2]*2라고 했을 때 한가지 경우가 이미 DP[i-1]의 경우에 포함되는 것이였다.
그래서 겹치지 않게 case를 잘 나눠서 점화식을 세우는 것이 중요할 것 같다.
백준 11659 : 구간 합 구하기 4
문제
코드
#include <iostream>
using namespace std;
int DP[1000004];
int SUM[1000004];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>DP[i];
SUM[i]=SUM[i-1]+DP[i];
}
for(int i=0;i<m;i++){
int start,end;
cin>>start>>end;
cout<<SUM[end]-SUM[start-1]<<"\n";
}
}트러블슈팅
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
백준 12852 : 1로 만들기 2
문제
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int DP[1000001];
int main(){
int N;
cin>>N;
DP[2]=1;
DP[3]=2;
for(int i=3;i<=N;i++){
vector<int> v;
if(i%2==0)
v.push_back(DP[i/2]);
if(i%3==0)
v.push_back(DP[i/3]);
v.push_back(DP[i-1]);
auto result=min_element(v.begin(),v.end());
DP[i]= *result+1;
}
// for(int i=1;i<=N;i++)
// cout<<DP[i]<<" ";
// cout<<"\n";
int cnt = DP[N];
int index=N;
cout<<cnt<<"\n";
cout<<index<<" ";
while(cnt--){
//index가 N-1 , 3으로 나누어지면 N/3 , 2로 나누어지면 N/2
//세가지 경우 비교해서 min_element찾고
//그 index의 DP[index] 출력
vector<pair<int,int>> reverse_v; //값 , index
if(index%3==0)
reverse_v.push_back({DP[index/3],index/3});
if(index%2==0)
reverse_v.push_back({DP[index/2],index/2});
reverse_v.push_back({DP[index-1],index-1});
auto result = min_element(reverse_v.begin(),reverse_v.end()); //값으로 비교
//result의 second값을 index에 저장
// for(auto iter:reverse_v)
// cout<<"("<<iter.first<<" , "<<iter.second<<")"<< " ";
index=result->second;
cout<<index<<" ";
}
}백준 12865 : 평범한 배낭
문제
코드
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int dp[101][100001];//dp[물품 개수][최대로 넣을 수 있는 무게]
vector<pair<int,int>> v;//{Weight,Value}
int main(){
int N,K;
cin>>N>>K;
v.push_back({0,0});
for(int i=0;i<N;i++){
int W,V;
cin>>W>>V;
v.push_back({W,V});
}
for(int i=1;i<=N;i++){
for(int j=1;j<=K;j++){
if(v[i].first>j){
dp[i][j]=dp[i-1][j];
}
else{
int m_weight=v[i].first;
int m_value=v[i].second;
dp[i][j]=max(dp[i-1][j],m_value+dp[i-1][j-m_weight]);
}
}
}
// for(int i=1;i<=N;i++){
// for(int j=1;j<=K;j++){
// cout<<dp[i][j]<<" ";
// }
// cout<<"\n";
// }
cout<<dp[N][K];
}
DevOps를 기반으로 한 클라우드, 알고리즘, 백엔드 관심있는 컴공생