목록전체 글 (104)
개발자 김수진
처음에 아래와 같이 정말 단순하게 풀었더니 시간초과가 나왔다. 생각해보니 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
#include using namespace std; //1인 경우는 시계 방향이고, -1인 경우는 반시계 방향 // N극은 0, S극은 1로 나타나있다. int K; //회전 횟수 int wheel[4][8]; int tmp[4][8]; void rotate(int idx, int dir) { if(dir ==1 ){ for(int i=0;i
Input 값을 cin으로 받아와서 한줄씩 다 받아오기 때문에 에러 발생 전형적인 BFS 문제로 현재 위치를 기준을 좌,우,상,하를 다 따져보고 조건에 따라 queue에 push //입력값 잘 구분하기 #include #include #include #include using namespace std; int map[25][25]; int N; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; vector v; int cnt =1; void BFS(int x ,int y) { cnt++; queue q; q.push(make_pair(x,y)); map[x][y]=cnt; int num=1; while(!q.empty()){ int x1 = q.front().first..