맛있는감귤

문제 : https://www.acmicpc.net/problem/1759조건을 만족하는 부분집합을 출력하는 문제입니다. 일반적으로 dfs로 많이 풀긴하는데 저는 비트마스크로 해결했습니다.최소 모음 1개, 자음 2개 이상을 포함한 구문만 출력해야된다는 것만 명심하시면 될 것 같습니다.비슷한 문제로 로또 문제가 있습니다.https://www.acmicpc.net/problem/6603 #include #include #include using namespace std; int L,C; char c[16]; void code(int n){ int place[16], consonants = 0, vowels = 0; int a = n, cnt = 0; for(int i=C-1;i>=0;i--){ place[i..

문제 : https://www.acmicpc.net/problem/2583출처Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 고등부 2번 저는 맵을 만든 후 사각형 부분은 전부 1로 하고 나머지 0이 되는 부분만 DFS를 이용하여 넓이를 구한 후 벡터에 넣어주고 사이즈( 사각형의 개수)를 출력 한 뒤 정렬하여 넓이를 출력했지만 우선순위 큐에 넣으면 간단하게 해결됩니다. #include &ltiostream&gt #include &ltalgorithm&gt #include &ltvector&gt using namespace std; int M,N,K; bool map[102][102]; bool isVisited[102][102]; vector&ltint&gt v; int px[..

문제 : 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