노는 게 제일 좋아

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

그렇게 어렵진 않은 백트래킹 문제였다. 역시나 초기화 하지 않아서 틀린...아주 기초적인 문제다. 시간도 아주 여유로운 문제였다. https://www.acmicpc.net/problem/14889 #맞는 풀이 #include #include #include // 절댓값 using namespace std; int N; int num[21][21]; // 최대 20명의 상대점수를 넣어놓음. (1~20만 씀 0 안씀) int m = 10000; //최솟값 (임의로 크게 잡아놓음) bool check[21]; // 팀원으로 뽑혔는지 확인해야함 (1~20만 쓸거임 0 안씀) vector target; // 뽑은팀 (숫자) void func(int cnt) { //절반을 뽑았을 때 //10몀 뽑은 팀과 남은 팀..

이 문제는 맞게 풀더라도 시간초과가 나는 문제다.. 내가 시간초과가 어디서 났는지 잘보도록하자. https://www.acmicpc.net/problem/2580 #1 시간초과 케이스 #include #include using namespace std; int pane[9][9]; // 9*9 게임판 bool check = false; // 답을 찾았는지 체크 vector vec; // 채워야 할 곳의 좌표 int number = 0; // 채워야 할 곳의 개수 //조건 1.가로의 합 45, 2.세로의 합 45, 3.3*3 내의 합 45 를 이용해보자.(비효율적..) // -> 하나의 행에 숫자가 중복되면 안됨, 하나의 열에... 하나의 3*3안에... // 해당 위치의 값으로 조사 bool numChe..

백트래킹 문제다. 풀다 보니 감이 조금씩 온다. https://www.acmicpc.net/problem/15652 조금씩 감이 오긴 온다. #맞는 풀이 #include #include using namespace std; int N, M; vector vec; void func(int cnt) { if (cnt == M) { //선택 종료 시 for (int n : vec) { cout

쉬운 문제지만 sort에서 cmp를 이용하는 문제고 문자열을 이용해서 익혀볼만 하다. https://www.acmicpc.net/problem/1181 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - set처럼 vector에서도 중복된 것들 없애기, unique() 위 글이 도움이 될 것이다. #맞는 풀이 #include #include #include #include using namespace std; int N; vector vec; bool cmp(string s1, string s2){ //길이가 작은 것이면 앞으로 if(s1.length() < s2.length()){ return true; }else if(s1.length() == s2.length()){ // ..

어렵지 않았지만 방법이 조금 틀렸다. https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net find에 대한 오해가 생겨서 시간 초과가 났다. # 시간 초과 풀이 #include #include #include #include using namespace std; int N; vector vec; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N; ..

백트래킹의 응용 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