노는 게 제일 좋아

이 문제는 맞게 풀더라도 시간초과가 나는 문제다.. 내가 시간초과가 어디서 났는지 잘보도록하자. 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일차에 상담을..

포도주시식이란다. 이것도 역시 다이나믹 프로그래밍이다. 근데 이 문제도 감이 올 듯 안온다. 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

역시나 그렇게 어렵지 않은 문제다. https://www.acmicpc.net/problem/2684 다만 문자열 계산할 때 내가 짚고 넘어가야 할 부분이 있었다. #맞는 풀이 #include #include using namespace std; int n; string target[8] = { "TTT","TTH","THT","THH","HTT","HTH","HHT","HHH" }; int num[8]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; while (n--) { string test; cin >> test; for (int i = 0; i < 38; i++) { string s; s = s + test[i] + test[i+1] ..

이 문제는 쉬우면서도 출력을 어렵게해서 난이도를 높인 문제라고 볼 수 있다. 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..