본문 바로가기

Problem Solving/BOJ 백준

 (132)
[ BOJ 백준 1351번 - 무한 수열 ] 해설 및 코드 https://www.acmicpc.net/problem/1351 목적 점화식을 풀어 An을 구하자. 접근법 1. An이 x*A0 꼴이 될 때까지 map에 넣고 반복하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #define f(i,l,r) for(int i=l;i>n>>p>>q; map m;m[n]=1; while(true){ map::iterator it=m.end(); if((--it)->first==0)break; m[it->first/p]+=it->second; m[it->first/q]+=it->second; m.erase(it); } cout
[ BOJ 백준 1269번 - 대칭 차집합 ] 해설 및 코드 https://www.acmicpc.net/problem/1269 목적 두 집합의 합집합에서 교집합을 빼자. 접근법 1. 두 집합을 정렬하여 앞에서부터 차례로 비교해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #define f(i,l,r) for(int i=l;i>a>>b; f(i,0,a)cin>>A[i]; f(i,0,b)cin>>B[i]; sort(A,A+a); sort(B,B+b); int i=0,j=0,ans=0; while(i
[ BOJ 백준 3482번 - Labyrinth ] 해설 및 코드 https://www.acmicpc.net/problem/3482 목적 임의의 free block 2개를 연결했을 때, 그 길이의 최대값을 구하자. 접근법 1. 백준 1967번 - 트리의 지름 문제와 같은 문제라고 보면 된다. 2. 인접한 free block으로 이동할 수 있고, 임의의 free block 2개 사이에는 길이 1개만 있다는 문제의 조건에 따라, Labyrinth는 트리구조를 갖는다. 3. 모든 period를 이어서 이를 트리의 형태로 보면, 어느 지점을 트리의 노드로 보아야 하는지 명확해질 것이고, 위 문제와 동일하다는 것을 알 수 있을 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30..
[ BOJ 백준 2533번 - 사회망 서비스(SNS) ] 해설 및 코드 https://www.acmicpc.net/problem/2533 목적인접한 두 개의 정점중 하나는 무조건 얼리 어답터여야 하며, 이 조건 하에 얼리 어답터의 최소 인원수를 구하자. 접근법1. 동적 계획법으로 접근하자. 인접한 정점은 조건에 따라 얼리 어답터로 선정하여 최소 값을 도출해 낸다. 12345678910111213141516171819202122232425262728293031323334353637#include#define f(i,l,r) for(int i=l;i>n; f(i,1,n){ int u,v;cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } memset(s, -1, sizeof(s)); cout
[ BOJ 백준 1949번 - 우수 마을 ] 해설 및 코드 https://www.acmicpc.net/problem/1949 목적 우수 마을 선정 기준('우수 마을'은 서로 인접할 수 없고, '우수 마을'이 아닌 마을은 '우수 마을'과 인접해야 한다.)에 따라, N개의마을중 몇개의 마을을 우수마을로 선정하여 인원의 합이 최대가 되게 만들자. 접근법 1. 트리의 성질에 따라 사이클에 관한 고민을 하지않아도 된다. 2. 우수 마을이 아닌 마을이 몇개 까지 인접가능한지 따위의 것을 고려하지 않아도 된다. 그냥 인접해도 무방하다는 가정으로 설계해도 최대값을 구하는 과정에서 걸러진다. 3. 우수마을과 인접한 마을만 우수마을에서 제외시키는 조건만 가지고, 간단히 DP로 해결하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..
[ BOJ 백준 1967번 - 트리의 지름 ] 해설 및 코드 https://www.acmicpc.net/problem/1967 목적 두 노드 사이의 경로 길이의 최대값을 구하자. 접근법 1. DFS로 부분 트리의 자식 노드들을 살펴, 자식 노드를 거쳐 갈 수 있는 가장 긴 길이를 두 개를 더해 트리의 지름을 만들고 최대값을 갱신한다. 2. 가장 긴 길이는 반환 값으로 넘겨줘서, 그 값을 부모 트리에서 다시금 사용할 수 있게 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include using namespace std; vector t[10001]; int ans=0; int sol(int i) { int a=0, b=0; for (auto e : t[i]) { int..
[ BOJ 백준 4256번 - 트리 ] 해설 및 코드 https://www.acmicpc.net/problem/4256 목적 이진트리의 전위 순회와 중위 순회 결과가 주어졌을 때, 후위 순회 결과를 구하자. 접근법 1. 다음 그림을 보자. 3은 루트 노드, 파란 부분과 노란 부분은 각각 루트 노드의 왼쪽과 오른쪽 노드들이다. 세번째 후위 순위의 그림을 보면, 나머지는 어떤 수인지 몰라도, 파란 부분의 노드들과 노란 부분의 노드들 순으로 나온뒤에, 루트 노드가 맨 마지막으로 나온다는 것을 알 수있다. 2. 두 가지의 배열(전위, 중위 순회)로 어떻게 마지막과 같은 형태로 만들 수 있을까?(아래 코드의 sol() 함수 참고...) 부분 트리 단위로 접근해야하며, 이를 재귀적으로 구현한다. 전위 순회 배열을 부분 트리로 이용할 것이며, 중위 순회 배열은 부분 트..
[ BOJ 백준 2250번 - 트리의 높이와 너비 ] 해설 및 코드 https://www.acmicpc.net/problem/2250 목적 입력으로 주어지는 노드의 정보로 트리구조를 형성하고, 각 레벨의 너비가 최대인 레벨과 너비를 구하자. 접근법 1. DFS를 이용하여 왼쪽 자식, 부모, 오른쪽 자식 순으로, 트리의 각 노드에 열번호를 지정한다. 2. 번호를 지정하면서 레벨 정보를 같이 넘겨주어, 각 레벨의 좌우 양 끝 노드의 열 번호를 갱신한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #define LEN 10001 #define f(i,l,r) for(int i=l;i>n; f(i,1,n..

티스토리툴바