전체 글 썸네일형 리스트형 14225번 14225번 - 부분수열의 합 단순한 조합 문제였다. 수열의 갯수도 최대 20개 이므로 시간복잡도는 O(2^20)이 된다. 따라서 완전탐색으로 충분히 해결할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#include using namespace std;#define MAX 2000001int N;int S[20];int num[MAX];void go(int k,int sum){ if (k == N) { num[sum] = 1; return; } go(k + 1, sum + S[k]); go(k + 1, sum); }int main(){ cin >> N; for (int i = 0; i > S[i]; go(0,0);.. 더보기 2422번 2422번 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 처음에는 오름차순으로 모든 경우의 수를 구하고, 기저 조건에서 모든 M번의 for문을 수행하면서 섞으면 안되는 조합이 있는지를 검사하는 방식을 구현했었다. 그런데 최악의 경우 200개 중에서 3개를 고르는 조합의 수 * 10000번의 for문을 돌게 되면 시간초과가 발생하게 된다. 따라서 M이라는 변수는 배열을 이용해서 저장하고, 최대한 200이라는 N의 값을 이용해서 문제를 풀어야 했다. 그래서 3개의 아이스크림만 고르면 되기 떄문에 first second third 를 재귀함수를 이용해서 구하면서 마지막에 먹어도 되는 조합인지 아닌지 를 판단하는 방식으로 코드를 구현했다. 12345678910111213141516171819202122232.. 더보기 3184번 3184번 - 양 해당 영역마다 BFS를 이용해서 문제를 풀 수 있었다. 처음에 탈출하는 영역 예외 처리를 해줘야 한다고 생각했는데, 문제를 읽어보니 양과 늑 대는 모두 영역 안에 존재한다는 조건때문에 그냥 각 영역에서 BFS를 실행하면 되는 문제였다. 각 영역에서 BFS를 실행하여, 해당 영역의 양의 수와 늑대의 수를 구하고, 늑대가 많거나 같으면 늑대를 최종 늑대 개수에 더해준다. 그 반대 의 경우에는 양의 수를 최종 양의 개수에 더해준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include#i.. 더보기 15661번 15661번 - 링크와 스타트 '스타트와 링크' 문제랑 흡사하게 만든 다른 문제이다. 기존문제랑 다르게 이 문제는 팀을 절반으로 나누지않아도 된다. 그냥 1명이상 팀이 유 지되면 된다는 조건이 있기 때문에 약간 다르다. 나는 그냥 완전탐색을 통해, 1번팀으로 뽑는다/ 뽑지 않는다 이런방식으로 완전탐색을 진행하였다. 왜냐하면 N제한이 20이기 때문에 시간복 잡도가 O(2^20) 으로 충분히 실행이 가능하다고 생각했기 때문이다. 하지만 이런 방식은 중복되는 값들을 다시 한번 계산하게 되므로 좀 더 시간 복잡도를 줄여서 풀 수 있을 것 같다. ( 빨리 푸신 분들은 DP로 접근한 듯 하다) 중복된다는 것은 i번 사람을 1번 팀으로 뽑고, 전부다 2번 팀으로 뽑는 경우와 i번 사람을 2번 팀으로 뽑고, 나머지를 .. 더보기 4991번 4991번 - 로봇 청소기 문제에서 쓰레기의 값이 10개 이하이고, 맵에서 vertex 의 최대 갯수가 400개가 된다는 것을 파악하였다. 따라서 플로이드 워셜 알고리즘은 시간 복잡도가 O(N^3) 이고 , 400^3 은 6천만정도 되기 때문에 가능하다고 생각하고 문제를 풀었다. 하지만 이 문제는 독특하게도 테스트케 이스가 while문을 통해서 한꺼번에 여러개가 실행되므로 최대 6천만을 여러번 돌리다보면 시간초과가 발생하게 된다. 따라서 이제는 각 쓰레 기마다 BFS를 이용해서 로봇,쓰레기들의 최소거리의 모든 쌍을 구해야 했다. 따라서 dirt 라는 벡터에 로봇의 위치와 쓰레기들의 위치를 모두 저장해주었다. 그 다음 for문을 이용해서 모든 쓰레기들에서 BFS를 돌리고, 다른 쓰레기들과의 거리를 D라는 .. 더보기 15662번 15662번 - 톱니바퀴(2) 톱니바퀴 1과 똑같은 문제, 예전에 풀었던 문제 다시 풀어보는 느낌으로 풀어보았다. 비교해보니 마지막 정답을 구하는 부분과, N의 크기가 달라졌다. 재귀에서 일단 현재 톱니바퀴를 회전시킨다. (단, 회전시키기 전의 3시와 9시 값을 미리 저장한다.) 그 다음으로는 진행 방향의 톱니의 특정 위치의 값과 비교한다. 이때 합이 1이면 S극 과 N극으로 구성된 것이므로 회전시킨다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include#.. 더보기 15486번 15486번 - 퇴사(2) 기존의 퇴사 문제와 같다. 하지만 N제한이 커졌기 때문에 기존 문제처럼 완전탐색으로 해결할 수 없다. (시간복잡도가 최대 N^2 이 되기 때문에) 그리고 int 형 변수를 사용할지 long long 을 사용할지 확인해보면 P의 최대값이 1000이고, N의 1500000 이므로, 최대값은 15억으로 int 형 변수로 충분히 해결할 수 있다. 최종적으로 DP를 이용해서 문제를 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940#include#includeusing namespace std;#define MAX 1500001int N;int P[MAX];int T[MAX];int D[MAX.. 더보기 15658번 15658번 - 연산자 끼워넣기(2) 기존에 있던 연산자 끼워넣기 문제와 똑같다. 다만 최대값과 최소값을 모두 구해야 한다는 차이점이 있다. N의 범위가 최대 11이기 때문에, 시간복잡도는 최대 4^11 로 완전탐색으로 충분히 구현할 수 있게 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#includeusing namespace std;int N;int num[12];int op[4];int MAX = -2000000000;int MIN = 2000000000;void go(int k,int sum){ if (k == N) { if (sum > MAX) MAX = s.. 더보기 이전 1 2 3 4 5 ··· 61 다음