노는 게 제일 좋아

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

다이나믹 프로그래밍의 문제는 뭔가 자꾸 많이 시킨다. 그래서 이게 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

음 이제부터 무조건 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 ..

전형적인 백트래킹 문제다. 백트래킹에 익숙하지 않은 터라 다른 사람풀이를 봐도 이해가 시간이 걸렸다. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹은 제일 인간다운 생각이 아닌가 싶다. 그리고 무의식적으로 그것이 효율적이라 생각하면서 쓰고 있다. 우선 나는 그렇다. 우선 이 문제를 보자마자 같은 줄에 못놓겠구나 생각이 들었다. 아무튼 거기까지만 하고 들어가보자 한줄에 하나 넣어보고 다음 줄에 되는 것 넣어보고 그 다음줄에 되는 것 넣어보고 하면 될 ..