본문 바로가기

Problem Solving

 (135)
[ BOJ 백준 1300번 - K번째 수 ] 해설 및 코드 https://www.acmicpc.net/problem/1300 목적 N*N 크기의 배열 A가 있다. A[i][j]에 i*j를 채워 넣고, 원소를 정렬하여 1차원 배열 B에 넣는다. 이때 B의 K번째 원소를 구하라. 접근법 1. 이분탐색으로 원소를 정하고, 좌우 범위 이동은 원소 크기 이하의 모든 원소 개수를 기준으로 한다. 2. 모든 원소의 개수는 O(n)으로 구해주자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #define f(i,l,r) for(int i=l;i> n >> k; int l = 1, r = k; while (l = k) r = num - 1; else l = num + 1; } cout
[ BOJ 백준 3020번 - 개똥벌레 ] 해설 및 코드 https://www.acmicpc.net/problem/3020 목적 1에서 H의 높이로 동굴을 일직선으로 통과하는 동안에, 만나는 장애물의 최소 개수와 그 때의 경로의 개수를 구하자. 접근법 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 #include #define f(i,l,r) for(int i=l;i> n >> h; n /= 2; f(i, 0, n) { int a, b; cin >> a >> b; --s[a]; ++s[h - b]; } int mn = n, cnt = 1, curr=n; f(i, 1, h) { curr += s[i]; if (c..
[ BOJ 백준 1939번 - 중량제한 ] 해설 및 코드 https://www.acmicpc.net/problem/1939 목적 섬과 섬 사이에 중량제한 데이터가 주어질 때, 공장이 있는 섬을 연결하는 경로중에 중량제한이 가장 큰 경로를 구하자. 접근법 1. 이분탐색으로 중량을 구한 후, dfs나 bfs로 검증한다. 두 가지 방법으로 테스트해 보았다. 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #include #define f(i,l,r) for(int i=l;i>..
[ BOJ 백준 11437번 - LCA ] 해설 및 코드 https://www.acmicpc.net/problem/11437 목적 트리에서 두 정점이 주어질 때, 최소 공통 조상을 찾자. 접근법 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 30 31 32 33 34 35 36 37 38 39 40 #include #include #define f(i,l,r) for(int i=l;i>n; while(--n){ int a,b;cin>>a>>b; m[a].push_back(b); m[b].push_back(a); } t[..
[ BOJ 백준 16434번 - 드래곤 앤 던전 ] 해설 및 코드 https://www.acmicpc.net/problem/16434 목적 던전의 모든 용을 쓰러뜨리기 위한 용사의 최대 체력을 구하자. 접근법 1. 이분 탐색으로 푼 사람들도 많지만, 이 문제는 구현문제다. 그냥 O(n)의 시간복잡도로 풀자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include using namespace std; typedef long long ll; int main(){ ios_base::sync_with_stdio(false);cin.tie(0); ll n,atk;cin>>n>>atk; ll curr=0, mx=0; while(n--){ int t,a,h; cin>>t>>a>>h; if(t=..
[ BOJ 백준 3649번 - 로봇 프로젝트 ] 해설 및 코드 https://www.acmicpc.net/problem/3649 목적 구멍을 막을 수 있는 차이의 절대값이 가장 큰 조각 2개를 찾자. 접근법 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 30 31 32 #include #include #define f(i,l,r) for(int i=l;i>n; int a[(int)1e6];f(i,0,n)cin>>a[i]; sort(a,a+n); int l=0,r=n-1; while(l
[ BOJ 백준 3056번 - 007 ] 해설 및 코드 https://www.acmicpc.net/problem/3056 목적 n명의 요원과 각 요원의 미션별 성공 확률이 주어질 때, 미션당 요원을 한명씩 배치하여 모든 미션을 수행할 때, 가장 높은 성공 확률을 구하자. 접근법 1. 완전 탐색 알고리즘을 구현해야 하며, 비트마스크를 이용해서 접근한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #include #define f(i,l,r) for(int i=l;i>a[i][j]; cout.precision(6); cout
[ BOJ 백준 3980번 - 선발 명단 ] 해설 및 코드 https://www.acmicpc.net/problem/3980 목적 11명의 선수의 포지션 별 능력치가 주어지고, 각 포지션에 배치했을 때 능력치의 최대합을 구하자. 접근법 1. DFS 완전탐색으로 접근하자. 2. 포지션에 능력치가 0인 선수는 배치 불가하니 이에 대한 처리를 해준다. 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 #include #include #include #define f(i,l,r) for(int i=l;i

티스토리툴바