목록알고리즘/백준 (65)
개발자 김수진
처음에 아래와 같이 풀었는데 메모리 초과 발생. 아무래도 2차원 배열에 의해서 메모리 초과가 발생한 것 같다. int형 약 4억 개면 1.6GB 정도 되는데 문제 조건에서는 메모리가 256MB로 제한되어 있다. #include #include using namespace std; int N,M; int map[20002][20002]={0,}; int dis[20002]={0,}; int main(void) { queue q; int start,end; cin >> N >> M; for(int i=0;i> start >> end; map[start][end]=1; } q.push(1); dis[1] = 0; while(!q.empty()){ start = q.front(); q.pop(); for(int..
처음에 아래와 같이 정말 단순하게 풀었더니 시간초과가 나왔다. 생각해보니 input의 개수가 1,000,000 개가 되면 시간이 O(NM)이 되어 시간 초과가 나올 것이다. #include #include using namespace std; // N : 나무의 수 , M : 집으로 가져가려는 나무의 길이 int N,M; int tree[1000000]={0,}; int MAX=0; int main(void) { vector tree; cin >> N >> M; for(int i=0;i> len; tree.push_back(len); if(MAX = 0){ int height=0; MAX--; for(int i=0;i MAX) heig..
#include #include using namespace std; //Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치 //번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. int N; int visited[20]; int ability[20][20]; int MIN = 999999999; void solve() { int s=0; int l=0; for(int i=0;i
중복 가능, 오름차순 맨 처음에 아무 생각 없이 풀었다가 1 3 1 1 2 1 이런 것들도 가능하게 해서 틀렸다 DFS 함수에서 재귀할 때 idx 인자를 i로 바꿔주니 맞았다. #include #include using namespace std; vector v; int N,M; void DFS(int cnt, int idx) { if(cnt == M ){ for(int i=0;i
DFS if문에서 return 안해줘서 처음에 답 이상하게 나왔다. 미친거 아닌가 어떻게 return을 빼먹지 #include #include using namespace std; int N,M; vector v; void DFS(int cnt) { if(cnt == M){ for(int i=0;i
N과 M(1)에서 DFS의 매개변수로 index를 추가해주어 오름차순 조건을 맞춰줬다. 처음에 main에서 DFS 호출할 때 for문 사용해서 결과가 제대로 안나왔는데 진짜 DFS 이해를 아직 제대로 못한 것 같다. #include using namespace std; int N,M; int visited[8]; void DFS(int cnt, int idx) { if(cnt == M) { for(int i=0;i
보자마자 DFS 기본 문제 같았다 근데 당연히 맞을 줄 알았는데 시간초과 나와서 당황했다 알고보니 endl 대신 '\n' 이거 하나 바꿔주니 바로 맞았다. endl이 시간 많이 잡아먹는듯 하다. 앞으로는 절대 안써야지 #include #include using namespace std; int N,M; int visited[8]; vector v; void DFS (int cnt) { if(cnt == M) { for(int i=0;i