맛있는감귤

문제 : https://www.acmicpc.net/problem/1967한 노드를 기준으로 가지고 있는 말단 노드를 쫙 땡겼을 때 가장 긴 녀석의 지름을 구하는 문제입니다.자식 노드가 3개 이상일 수 있다는 것만 조심하시면 DFS로 간단하게 해결 가능합니다.자식 노드의 가중치의 합을 return 하여 기준 노드에서 가장 긴노드, 두 번째 노드를 구해서 더한 값이 지름이 됩니다. #include #include using namespace std; int N, ans=0; vector v[10001]; int dfs(int start){ int fst=0, snd=0, sum; for (auto n : v[start]){ //printf("%d %d\n",start,n.second+len); sum = ..

문제 : https://www.acmicpc.net/problem/1193간단한 문제라고 생각했는데 생각보다 애먹은 문제였습니다.수학적 공식이 있지 않을까 찾다가 포기하고 좀 무식하게 직관적으로 해결했습니다.대각선을 하나의 군으로 봤을 때, 군의 갯수는 n의 개수만큼 있습니다. 게다가 홀수와 짝수에 따라 방향이 달라지는 것도 포인트입니다.그렇기 때문에 홀수일 경우 N/1로 시작해 분자A를 -- 분모B를 ++해주면 되고 짝수일 경우엔 반대로 해주면 됩니다. #include int main(){ int X,n=1,cnt=0,A=1,B=1; scanf("%d",&X); while(1){ if(n%2==0) A=1, B=n; else A=n, B=1; for(int i=0;i

문제 : https://www.acmicpc.net/problem/6603출처Contest > University of Ulm Local Contest > University of Ulm Local Contest 1996 F번 비스마스킹을 이용해 brute force로 해결했습니다.6개의 번호안에 들어가냐 마냐의 차이기 때문에 그렇고 또 이렇게해서 사전 순으로 출력이 가능하기 때문입니다.N의 갯수만큼 들어오는 i 값을 2진수로 변환 한뒤 0(6개 번호안에 포함되는 숫자) 가 6개인 녀석만 출력해주었습니다. #include #include void print(int num[], int i_num, int N){ int place[13], cnt=0, exc = N-6; bool flag = true; fo..

문제 : https://www.acmicpc.net/problem/5430출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 I번 덱(deque)을 이용하면 간단하게 해결할 수 있는 문제입니다.R명령어가 들어왔을 때, pop하는 방향만 잘 잡아주면 되고D명령어가 들어왔을 때, empty 인지 검사를 하고 error를 출력하면 됩니다.입력받을 때 수열이 더럽게 주어져서 아래와 같이 무식한 방법으로 해결했는데다른 분들 코드를 보니 getchar(), scanf("%d",X[i]); 의 반복으로 간단하게 입력 받을 수 있더군요. 좋은거 배웠..

문제 : https://www.acmicpc.net/problem/12761출처University > 전북대학교 > 2016 전북대 프로그래밍 경진대회 G번저는 문제를 잘못 이해해서 동규와 주미가 각 턴마다 움직인다는 줄 알았습니다.알고 보니 스카이 콩콩이 두개..여튼 문제 해결방법은 BFS를 이용해 각 시간마다 움직일 수 있는 거리를 다 Queue에 push하는 것 입니다. #include #include using namespace std; int A, B, N, M, ans = 0; bool visited[100002]; queue q; int main() { scanf("%d%d%d%d", &A, &B, &N, &M); q.push(N); visited[N] = 1; while (!q.empty(..

문제 : https://www.acmicpc.net/problem/2146제가 푼 방식에는 두 가지 핵심이 있습니다.먼저 각 섬의 모서리 부분을 찾고 각 모서리가 어느 섬의 것인지 구분하기 위한 라벨링 작업두 번째는 각 섬에 대한 모서리 간의 거리 비교입니다. 라벨링은 DFS로 돌면서 근처에 물이 있으면 vector에 삽입했습니다. 한 지점에서 주위에 물이 두 군데 이상이면 중복 삽입되기 때문에 flag를 이용해 제외시켜주었습니다. 거리 비교는 BFS로 하려다가 굳이 그럴 필요가 없을 것 같아 서로 다른 라벨을 가지고 있는 섬끼리 비교하며 그냥 좌표를 빼줬습니다. #include #include using namespace std; int map[102][102], no=2, N, ans=98765432..

문제 : https://www.acmicpc.net/problem/9328출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 Preliminaries K번 생각보다 많이 삽질한 문제였다. 최소 경로를 구하는 것은 아니기 때문에 열쇠가 없는 문은 대기 큐에 넣어 놓고 열쇠를 구했을 때 다시 큐에 넣어주는 방식으로 해결했다. 만약 입력받을 때 요소를 구분한다면 순서가 중요하다. 왜냐하면 A와 a가 전부 테두리에 있을 수도 있기 때문이다. #include &ltiostream&gt #include &ltqueue&gt using namesp..

문제 : https://www.acmicpc.net/problem/1182브루트 포스로 풀기엔 생각보다 까다로운 면이 있다. 부분 집합을 구할 때는 DP 혹은 비트마스크를 이용해서 많이 구하기 때문에부분집합을 구하는 기법을 알아두면 다른 곳에서도 유용하게 사용할 수 있다.나는 비트마스크로 풀었는데 비트마스크를 이용해 부분집합을 구하는 코드는 아래와 같다. int N[4] = {1, 2, 3, 4}; for(int i=0; i < (1

문제 : https://www.acmicpc.net/problem/1463 1차원 좌표에다가 증감이 아닌 감소만 하게 되는 연산이니 BFS로 풀 수 있을 것이라 판단하고 풀었다. #include &ltcstdio&gt #include &ltqueue&gt using namespace std; queue&ltint&gt q; bool visited[1000000]; int main(){ int N,cnt=0; scanf("%d",&N); q.push(N); while(!q.empty()){ int sz=q.size(); while(sz--){ int n = q.front(); q.pop(); if (n==1){ printf("%d\n",cnt); return 0; } if(n%3==0 && n/3&gt0 ..

문제 : https://www.acmicpc.net/problem/2979 출처Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #6 1번 시뮬레이션 문제지만 반복문 없이 풀 수 있지 않을까 고민했지만 생각이 나지않아 말 그대로 시뮬레이션처럼 풀었다. 트럭의 구분없이 몇대가 있느냐만 고려해주면 되는 문제이다. #include &ltcstdio&gt #include &ltqueue&gt using namespace std; int main(){ int A,B,C,cnt=0,ans=0; priority_queue&ltpair&ltint, bool&gt&gt q; scanf("%d %d %d",&A,&B,&C); for(..