노는 게 제일 좋아

어렵지 않았지만 방법이 조금 틀렸다. 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/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..

음 이제부터 무조건 float 절대 안 쓰고.. double 써야징 ㅎㅎ 물론 메모리는 더 먹지만.. float으로 오차가 생기는 것보단 훨씬 낫다. https://www.acmicpc.net/problem/2108 # 맞는 풀이 #include #include #include #include using namespace std; //산술 평균을 위해 필요한 값 - 원소의 개수, 원소의 합 //최빈값 "" - 해당 원소의 출현 횟수 //중앙값 - 해당 원소를 내림차순 또는 오름차순으로 정렬 -> but 항상 홀수의 개수를 가지므로 (원소 사이즈 + 1)/2 idx에 존재 //최대,최소 - 원소를 입력받으며 최소 최대값 갱신. //원소의 개수, 원소의 합을 위한 벡터 vector V; //최빈값 int n..

이 문제 또한.. 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를 만..

흠... 나는 처음에 BFS로 풀었는데 사람들이 DP라고 한다.. 그래서 둘다 풀어보았다. 시간제한이 아주 짧은 것으로 보아... 그렇다. DP가 확실하였구나 1초에 5억번 연산이라치면.. 1/6 대충 8천만번이면 되겠구나. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 먼저 BFS로 한 풀이 15분만에 푼 것 같다. #include #include using namespace std; int num[1000001]; int dist[1000001]; queue Q; int target; void init() { ios::sync_with_stdio(0);..

음.. 전형적인 구현 문제로 말하는 대로 구현하면 된다. 구현에 무엇을 쓸 지는 모두 사용자의 맘대로 다만 시간보다 메모리는 많기에 맘껏 써도 될 것 같다. https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 이건 내가 한 번에 못풀었다. 감은 왔는데 도저히 구현이 되질 않았다. 하지만 풀이를 보니.. 30%정도까지는 맞았더라.. 백트래킹을 써야지~ 생각은 했지만 백트래킹에서 탐색을 하지 못했다. #맞은 풀이(참고해서) #include ..

나 이거 맞았길래 봤더니 파이썬으로 풀었음 ㅎ 파이썬 permutation으로 3초만에 풀었음..ㅎ C++로 해보자꾸나.. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 백트래킹이라는 원리를 적용해서 푼다. 코드에 주석을 보면서 이해해보자 #include #include using namespace std; int n,m; /////////////////////////////////////// int arr[10]; // 선택에 ..