mojo's Blog

13308번: 주유소 (acmicpc.net) 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 다익스트라 문제이다. 이 문제를 해결할 때 특히 최소 비용이 MAX_INT 값을 넘어간다는 것을 캐치하지 못해서 많이 삽질한 문제이다. 문제를 해결함에 있어서 int 로 설정해야 할지, long long 으로 설정해야 할지 미리 파악을 해두는 것이 중요하다. ※ 문제 접근 ① 어떠한 지점 P 에 대해서 특정 기름(oil) 으로 마지막 지점까지 도달하는데 최소 비용에 대한 배열 설계가 필요하다...

문제 링크 : 10775번: 공항 (acmicpc.net) 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 공항에 G 개의 게이트가 존재하며 1, 2, ..., G 의 번호를 가진다. 비행기는 P 개가 순서대로 도착하며 i 번째 비행기는 1 번부터 \(g_{i}\) 번까지의 게이트중 하나를 영구적으로 도킹할 수 있다고 한다. 도킹할 수 없다면 현재까지 도킹된 횟수를 출력하는 문제이다. 이 문제는 유니온 파인드 알고리즘을 활용하여 해결하였고 다음과 같이 이미지를 형상화하여 해결하..

문제 링크 : 12013번: 248 게임 (acmicpc.net) 12013번: 248 게임 이 예에서, Bessie는 두 번째와 세 번째에 있는 1을 2로 합친다. (1 2 2) 두 번째와 세 번째에 있는 2를 3으로 합친다. (1 3) 첫 번째와 두 번째 1을 합치는 것은 최적해가 아님을 주의해라. www.acmicpc.net Bessie 는 두 개의 인접한 수가 같을 때 (인접한 수 + 1) 로 합칠 수 있다고 한다. 즉 이러한 작업을 계속 하여 더이상 진행이 되지 않도록 하는 수열에 대해서 가장 큰 수를 구하는 문제이다. 위 문제를 다이나믹 프로그래밍으로 \(O(N^{3})\) 시간복잡도로 해결했다. ※ 접근 방법 1. dp[l][r] 을 [l, r] 범위 내에 얻을 수 있는 최대 점수라고 설정하..

문제 링크 : 25308번: 방사형 그래프 (acmicpc.net) 25308번: 방사형 그래프 게임 캐릭터의 능력치를 한 눈에 보기 좋게 나타내는 방법으로 방사형 그래프가 있다. 캐릭터는 8개의 능력치를 갖고 있고 각 능력치를 $a_1, a_2, \cdots, a_8$이라고 하면, 그래프는 팔각형 형태이고 www.acmicpc.net 완전 탐색 및 수학 문제이다. 능력치 8개가 주어질 때, 블록 다각형이 만들어질 수 있는 모든 경우의 수를 구하는 문제이다. ※ 문제 접근 방법 ① permutation 을 이용하여 만들어질 수 있는 \(8!\) 가지 능력치를 배치한다. ② (\(a_{1}\), \(a_{2}\), \(a_{3}\)) 부터 (\(a_{8}\), \(a_{1}\), \(a_{2}\)) 까지 ..

문제 링크 : 25189번: 시니컬한 개구리 (acmicpc.net) 25189번: 시니컬한 개구리 개구리는 $N \times M$ 격자 모양의 청정한 서식지에 살고 있다. 가장 왼쪽 위 칸의 좌표는 $(1,1)$이고 가장 오른쪽 아래 칸의 좌표는 $(N,M)$이다. 각 격자 칸에는 개구리밥이 있는데, 개구리는 자신이 www.acmicpc.net 2022 서강대학교 청정수컵 Round G번 문제이다. 문제 유형은 전형적인 BFS 로 보이지만, 인풋 사이즈로 인해 난이도가 급상승한 느낌이다. N, M 값의 최대값이 100 이였다면 navie 하게 \(O(N^{3})\) 으로 해결이 가능했을 것이다. 그러나, N, M 값의 최댓값이 1000 이므로 navie 한 접근이 불가능하므로 약간의 생각이 필요했다. ..

문제 링크 : 24526번: 전화 돌리기 (acmicpc.net) 24526번: 전화 돌리기 첫 줄에 부원의 수 $N$과 관계의 수 $M$이 공백을 사이에 두고 정수로 주어진다. ($2 \le N \le 100,000$ , $1 \le M \le $ $500,000$) 둘째 줄부터 $M+1$번째 줄까지 어떤 부원 $U_{i}$가 전화를 받았을 때 다른 부원 www.acmicpc.net 사이클을 어떻게 처리해야 할지 고민을 했던 문제이다. 우선 방문배열을 2차원 배열 형태(visited[100001][2])로 선언하여 다음과 같이 처리하도록 하였다. visited[x][0] : 노드 x가 최초로 방문되었는지 판단하기 위한 용도이며 true로 마킹된 경우 방문한 경우다. visited[x][1] : DFS를..