노는 게 제일 좋아

DP문제다. 하지만 역시 문제를 생각하는데 오래걸렸다. 20분쯤 걸린듯..ㅠ 시간제한보면.. 무조건 DP란 것이 느껴진다. https://www.acmicpc.net/problem/1904 #맞는 풀이 #include #define X 15746 using namespace std; long long dp[1000001]; int N; int main(){ cin >> N; // 맨 끝의 타일이 00으로 끝나느냐 1로 끝나느냐의 차이를 생각해보자 dp[1] = 1; dp[2] = 2; //숫자가 너무 커지기 때문에.. 답이 제대로 나오지 않음 for(int i = 3; i

백트래킹의 응용 2번째 문제다. Bruteforce를 이렇게 푸는 것이 효율적이다. https://www.acmicpc.net/problem/15650 먼저 풀이부터 보자 # 맞는 풀이 #include #include #include using namespace std; int N, M; // N까지의 수, M개 선택 vector vec; int check[9]; // 사용체크 //현재 숫자보다 큰 것이 들어가게끔 해야함. void func(int cnt, int cur) { if (cnt == M) { for (auto c : vec) { cout > M; //1-N 까지의 수를 중복없이 M개 뽑아서 출력(오름차순) func(0, 1); } 처음에는 cnt만 집어넣어서 넣다보니 수열이 중복되어서 나왔다..

난 어려웠다. 생각이 났지만 어떻게 해야할지 몰랐다. https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 맞는 풀이를 보기 전에 설명부터 해보자. 이런 문제는 첫날과 i번째의 날일 때 어떤 상황일까 생각해봐야 한다. 첫날은 어떨까?? 만약 {5,10} 이고 다음날 {2,30}이 있다면 해야할까 말아야 할까? 즉, 뒤에 뭐가 있냐에 따라 할 것인가 하지 않을 것인가 정해진다는 말이다. 그렇다면 i번째가 마지막날이라고 해보자. i번째의 날은 해야할 까? i번째 날은 상담이 진행 중이면 당연히 못하고 2일 이상 걸리면 못한다. ?????? 진짜 모르겠다. 다시 생각해보자.. 1일차에 상담을..

//2022.04.07 다시 업데이트 음 나는 조금 어렵게 생각했나보다.. 남들은 쉽게 풀더라. https://www.acmicpc.net/problem/10814 우선 내 풀이는 이렇다. # 맞은 풀이 #include #include #include using namespace std; struct Id{ int order; int age; string name; }; //const와 &을 받아옴 bool comp(const Id &p1, const Id &p2){ if(p1.age< p2.age){ return true; } else if(p1.age == p2.age){ return p1.order < p2.order; }else{ return false; } } int N; vector v; in..

포도주시식이란다. 이것도 역시 다이나믹 프로그래밍이다. 근데 이 문제도 감이 올 듯 안온다. https://www.acmicpc.net/problem/2156 우선 풀이를 보자 #include #include using namespace std; int drink[10001]; int dp[100001]; int N; int main(){ cin >> N; for(int i = 1; i> drink[i]; } dp[1] = drink[1]; dp[2] = drink[1] + drink[2]; for(int i = 3; i

다이나믹 프로그래밍의 문제는 뭔가 자꾸 많이 시킨다. 그래서 이게 DP 문제구나라는 것은 감이 오지만 어떻게 적용해야할 지 감은 바로 안온다.. https://www.acmicpc.net/problem/1912 #맞는 풀이 #include #include using namespace std; int N; int num[100001]; int dp[100001]; int main() { cin >> N; for (int i = 1; i > num[i]; } int M = -1001; for (int i = 1; i = M) { M = dp[i]; } } cout

이 문제는 쉬우면서도 출력을 어렵게해서 난이도를 높인 문제라고 볼 수 있다. unsigned long long의 범위를 넘어서... 이건 문자열로 계산을 했어야했다. 그리고 너무 어이 없는 문제다.. 0일 때 값이 1이란다.. 넣을 수 없는 공간이 없다면 찬 것이라고 보는 것일까..? 2021.05.30 0에 대한 언급이 전혀 없다. 2 * n 즉, 2 * 0이면 타일을 넣을 수 가 없는데.. 우선 설명을 달라고 하긴 했다. https://www.acmicpc.net/problem/1793 #맞는 풀이를 보자. #include #include // reverse() 사용 #include using namespace std; string BigNumAdd(string a, string b) { string..

이 문제 또한.. DP로 즉, 이전 결과가 다음 결과에 쓰이는 문제라고 볼 수 있다. 추가 시간이 없다는 말은 언어마다 추가시간이 없다는 말 같다. C++은 항상 기준이 되므로 시간제한에 추가시간이 있을까 없을까 고민안해도 된다. 시간 초과나면 잘못푼거다 ㅎ https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 맞는 풀이 #include using namespace std; int num[11]; int main(){ int n; cin >> n; num[1] = 1; num[2] = 2; num[3] = 4; //왜 이렇게 되는가? // 4를 만..