2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 2631, 줄세우기 🔥난이도: Gold 4 📁 프로세스 [문제설명] KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼..

15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 15989, 1,2,3 더하기 4 🔥난이도: Gold 5 📁 프로세스 [문제설명] 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 1+3 (3+1) 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방..

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 4179, 불! 📌 난이도 : Gold 4 📌 알고리즘 : DFS & BFS 📌 자료구조 : Queue 간만에 코테를 준비하다보니 많이 해맸었다. DFS & BFS 와 Queue 를 사용하여 문제를 해결했다. 🧩 프로세스 📚 초기화 및 선언 : 불과 진수의 이동에 대한 정보를 가져야 한다. 해당 좌표까지 걸리는 시간을 담을 distF, distJ 와 좌표들을 담을 Queue 2개..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 2458, 키 순서 📌 난이도 : Gold 4 📌 알고리즘 : 플로이드 워셜 이번 문제는 이해하는데 많은 시간이 소요되고 구현까지도 꽤 많은 시간이 걸린, 개인적으로 복잡한 문제였다. 풀이를 간략하게 설명하자면 먼저사람들을 정점으로 간주한다. 모든 정점간의 거리를 INF 로 초기화 해주고주어진 연결관계를 이어주고, 플로이드 워셜을 통해 특정 사람이 모든 사람과의 거리를 체크해서 값을 갱신해준다. 2..

https://www.acmicpc.net/problem/1489 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 14891, 톱니바퀴 📌 난이도 : Gold 5 📌 알고리즘 : 구현 이번 문제는 생각할게 많은 구현문제다.회전할 톱니바퀴와 방향이 주어졌을 때, 모든 톱니바퀴의 맞닿는 좌측과 우측을 모두 조회해야 한다. 🧩 프로세스 📚 초기화 및 선언 : 톱니바퀴의 12시방향부터 4개를 순서대로 입력받아 넣어준다. (int) public static void input() throws IOException {..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2638, 치즈 📌 난이도 : Gold 3 📌 알고리즘 : DFS & BFS 이번 문제는 골드 3의 난이도지만 그렇게 어려운 문제는 아니였다. 외부공기와 외부공기가 유입되지 않는 구간만 잘 체크하면 된다! 문제를 잘 읽어보면 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다 는 말이 있다. 그렇다면 치즈가 아닌 공기가 유입될 수 있는 지역에서 DFS 로 모든 공기를 탐색하..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1937, 욕심쟁이 판다 📌 난이도 : Gold 3 📌 알고리즘 : DFS, DP 이번 문제는 모든 구간에 대해 무지성으로 DFS를 돌렸다가 가차없이 시간초과가 나와서 DFS + DP로 해결한 문제이다. 🧩 프로세스 📚 초기화 및 선언 : 숲의 크기 N을 기반으로 숲의 정보들을 입력한다. 📚 탐색 : 이동할 수 있는 칸의 수를 저장할 DP를 기반으로 탐색을 진행하며 최대값을 갱신해준다...

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 1167, 트리의 지름 📌 난이도 : Gold 2 📌 알고리즘 : DFS & 그래프이론 이번 문제는 임의의 두 점 사이의 거리 중 가장 긴 것, 지름을 구하는 문제이다. 모든 정점에 대하여 탐색을 진행하며 거리의 최대값을 구하면 되지만 정점의 개수가 100,000개 까지이다 보니 시간초과가 발생한다.그렇기에 다른 방안을 생각해보자. 임의의 정점에서 제일 멀리있는 정점의 길을 따라가..