본문 바로가기
반응형

Problem Solving242

백준 20529번 가장 가까운 세 사람의 심리적 거리 - C++ 풀이 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 2. 32명 초과인 경우 심리적 거리의 최솟값은 0이다. 3. 32명 이하인 경우 심리적 거리의 최솟값은 브루트포스로 구할 수 있다. 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 비둘기집의 원리란 "n+1 마리의 비둘기가 n개의 비둘기 집에 나누어들어간다면, 적어도 한 집에는 반드시 두 마리 이상의 비둘기가 들어가게 된다"는 원리이다. 이것을 현재 문제에도 적용할 수 있다. 사람 = 비둘기, mbti 종류 = 비둘기집으로 생각하면 된다. mbti가 16종류가 있으므로, 만약 사람이 16+1=17명 있다면, 적어도 한 mbti에는 .. 2023. 7. 6.
백준 14940번 쉬운 최단 거리 - C++ 풀이 1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다. 2. BFS의 출발 노드를 목표지점으로 설정하여 모든 칸까지의 거리를 한번에 계산한다. 1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다. 각 칸을 노드로 생각하고 갈 수 있는 땅끼리는 연결하여 그래프를 만든다. 이제 BFS를 사용하면 두 지점 사이의 거리를 구할 수 있다. 2. BFS를 사용하여 목표지점에서 모든 칸까지의 거리를 한번에 계산한다. 각 칸에서 출발하여 목표지점까지 도달하는 BFS를 수행한다면, 총 n^2개의 칸에 대해 O(n^2)의 시간복잡도가 소요되므로 총 시간복잡도는 O(n^4)가 되어 시간초과를 받을 수 있다. 거꾸로 목표지점에서 출발하여 모든 칸을 방문하는 BFS를 진행하면 한번에 계산이 가능하다. 각 노드를.. 2023. 7. 6.
백준 10800번 컬러볼 - C++ 풀이 1. 공들을 크기 오름차순으로 정렬한다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) 1. 공들을 크기 오름차순으로 정렬한다. 먼저 공들을 크기 기준으로 오름차순 정렬해준다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) i번째 공보다 크기가 작고 색이 달라야 하므로, (i번째 공보다 작은 공들) - (i번째 공보다 작고 색이 같은 공들)을 구하면 된다. 포인터를 하나 두고, 포인터가 가리키는 공의 크기가 현재 공의 크기와 같아지기 전까지 포인터를 오른쪽으로 이동시키면서 1. 전체 크기 합과 2. 색깔별 크기 합.. 2022. 10. 5.
백준 16954번 움직이는 미로 탈출 - C++ 풀이 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 시간이 지남에 따라 미로가 바뀌고 있으므로, 상태 노드를 나타내기 위해 필요한 값은 행, 열, 그리고 시간 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. BFS를 사용하여 시작 노드 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 언제 도착했는지는 상관이 없기 때문에 r=0, c=7인 노드인지만 확인하면 된다. #include #include using namespace std; typedef.. 2022. 9. 30.
백준 13305번 주유소 - C++ 풀이 1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다. 1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다. 기름통의 크기가 무제한이므로, 그리디하게 각 도시에 도착하기 전에 가장 싼 주유소에서 기름을 넣고 오면 최적이다. 일반화하면, i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 주유소에서 넣고 오면 된다. 이때 i-1번 도시에서 i번 도시까지의 거리를 dist[i], 1~(i-1)번 도시 중 가장 싼 주유소의 가격을 min_price[i]라고 하면 비용은 dist[i] * min_price[i]이다. #include using namespace .. 2022. 9. 27.
반응형

티스토리툴바