백준215 백준 13016 내 왼손에는 흑염룡이 잠들어 있다 (c++) 문제 URL : https://www.acmicpc.net/problem/13016 문제접근법 : 트리에서 모든노드중 가장 먼거리들을 전부 구하는문제입니다.이문제를 풀기위해서 트리의 지름을 확인해야합니다.트리의 지름을 확인해야합니다. 트리라는 성질로인해모든노드의 가장먼거리는 지름의 끝점이기때문에 그 끝점에서의 거리로 가장 먼거리를저장하기때문에 dfs를 3번만 돌리면 충분히 구할수있습니다. 소스코드 : //By 콩순이냉장고#includeusing namespace std;#define ll long longll n;vector> v[100000];vectorres;ll _max = -1;int start= -1;void input(){ cin>>n; ll a,b,c; for(int i =0.. 2024. 11. 30. 백준 7812 중앙트리 (Java) 문제 URL : https://www.acmicpc.net/problem/7812 문제 접근법 :모든 노드의 비용의 합을 다구하는 문제입니다.대표적인 트리 dp 문제인데 증명은 https://www.youtube.com/watch?v=T81Bpx2OmS4이 유튜브를 참고하는게 좋을것같습니다. leetcode 문제인데 이문제와 유사하며 거기에 가중치가 있을 뿐입니다. 간단하게 하나의 루트로부터 모든 비용을 구한후 다음 노드에서의 가중치의 합을 구할려면그 가중치로부터 노드의개수가 n일때 n-child의 개수만큼 비용을 똑같이 더해주고 그리고 -child의 개수만큼 빼줘야하는데n- child - child 의 공식이 나옵니다.그래서 가중치를 곱하면 끝입니다. 소스코드 : import java.io.*;.. 2024. 11. 30. 백준 12970 AB 문제 URL : https://www.acmicpc.net/problem/12970 문제 접근법 : 처음엔 전수조사해서 풀려고 했으나 2^50 이라 가능할것같지 않아서수학적으로 접근했습니다. 만약 ABBBBABB 가 있따면뒤에 있는B뒤에있는 B들은 전부 A의 개수만큼 더해줘야하기때문에01111022 가 되는 구조라처음부터 n의 길이만큼 B로 설정해줍니다.그럼 어딘가 k개 이하만큼 A를 잘 설정해줘야하는데n이 6이라고 가정하고 k에 상관없이처음 BBBBBB 로시작해0번째에 A를 놓는다고가정하면ABBBBB 가 되고 011111 만큼 count하면 5가 되고중간 아무 위치에 A를 넣을때 어떻게 카운트하냐면ABABBB일때 010222가 된다면 7이 되는데 A의 인덱스위치에서 n-1-i 만큼 카운트해주고 또 앞에.. 2024. 11. 15. 백준 20920 영단어 암기는 괴로워 문제 URL : https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 문제 접근법: 정렬기준대로 정렬하라는 문제입니다. 그러나 단어가 몇개나오는지는 map을 이용해야겠죠? map을 이용해서 m개이상인것을 추출하고 1,2,3번 각자 조건대로 정렬하시면됩니다. 소스코드: import sys from collections import Counter input = sys.stdin.read.. 2024. 1. 3. 이전 1 2 3 4 5 6 7 ··· 54 다음
