https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 1. Logic BFS로 노드를 지날 때 마다 거리를 더해주며 BFS를 돌면 된다. 입력을 받을 때 양방향으로 받아주고 m개를 입력 받을 때 마다 vis배열만 초기화 잘 시켜주면 된다. 2. Code #include using namespace std; int n, m; vector graph[1001]; bool vis[1001]; int BFS(int start, int e..
백준
https://www.acmicpc.net/problem/9656 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. Logic 돌 갯수가 짝수인지 홀수인지만 판단하면 된다. 돌 갯수가 짝수면 항상 상근이가 이기고 홀수이면 항상 창영이가 이긴다. 2. Code #include using namespace std; int n; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; if(n % 2 == 1) cout
https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 1. Logic 해당 문제를 환형으로 보지말고 그냥 직선형으로 봐서 0번째 색깔을 선택하는 경우와 0번째 색깔을 선택하지 않는 경우 2가지로 나눠서 해결했다. 0번째 색깔을 을 선택하는 경우는 1번째 색깔을 절대로 선택 못하기 때문에 인덱스를 2로 올려준 후 함수로 전달한다. 0을 선택하지 않는 경우는 1번 색깔을 선택해도 되고 안해도 되기 때문에 인덱스는 1, cnt는 0 으로 넣어준다 2. Code #include ..
https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net 1. Logic 입력을 받은것을 기반으로 숫자 입력을 받을 때 마다 vis배열에 체크를 하고 for문을 돌며 각 빙고 라인들을 체크해준다. 2. Code #include using namespace std; int bingo[5][5]; int vis[5][5]; int check1() { int ret = 0; for(int i = 0; i < 5; i++) if(vis[i][0] && vis[i][1] &&..
https://www.acmicpc.net/problem/2441 2441번: 별 찍기 - 4 첫째 줄에는 별 N개, 둘째 줄에는 별 N-1개, ..., N번째 줄에는 별 1개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. www.acmicpc.net 1. Logic 구현,,, 쉬운 구현,,, i만큼 공백 출력 i-공백만큼 별 출력 2. Code #include using namespace std; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { cout
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 1. Logic unordered_map을 사용해서 이름을 저장해준다. union find알고리즘을 사용하기 위해서 몇번째 노드인지 같이 넣어줬다. 즉 key값은 이름 value값은 고유 번호이다. 노드의 부모를 찾아서 merge해 줄 때 부모 노드의 친구 수를 더해주면 된다. 주의해야 할 점은 사람1의 부모와 사람2의 부모가 같을 경우 2번 더해주는 상황이 일어나기 때문에 더하지 않도..
https://www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 1. Logic 사전순으로 가장 빠른 것을 구하라고 했기 때문에 0은 뒤에서부터 없애주고 1은 앞에서 부터 없애주는게 가장 작은 숫자를 구할 수 있는 방법이다. 2. Code #include using namespace std; int zero; int one; int checkErase[501]; int main() { string str; string ans = ""; cin >..
https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 1. Logic 처음에 unordered_map으로 접근했다가 시간초과를 받았다. 키워드 입력을 받을 때 중복이 없기 때문에 삽입, 삭제 모드 O(1)을 시간복잡도로 가지는 unordered_set을 활용하여 풀이했다. 2. Code #include using namespace std; unordered_set us; unordered_set::iterator i..
https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 1. Logic 재료의 갯수 n이 10밖에 안되기 때문에 완전탐색으로 해결 가능하다. 조합 탐색을 하며 선택을 하는 경우 안하는 경우를 구해서 값을 선택 해 주면 된다. 2. Code #include using namespace std; vector taste; long long ans = LLONG_MAX; long long n; void solve(long long idx..
https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 1. Logic 여기서 비트는 한 물병으로 얼마나 물이 모였는지를 나타낸다. 항상 물은 똑같은 양끼리 합칠 수 있고 1부터 시작하기 때문에 1 > 2 > 4 > 8 > 16 등등 이렇게 2의 제곱수로 늘어나게 된다. 즉 1의 갯수는 물이 담긴 물병의 갯수를 의미한다. 테스트케이스인 13, 2를 예시로 들어보면 13을 2진수로 변환하면 1101이다. (8 + 4 + 1) 1이 먼저 나오는 위치는 0번째이..
