![]()
📕문제 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 🔎문제설명 bfs 문제에서 조금 변형이 있는 문제입니다. 스위치를 켜면 해당 방으로 이동할 수 있는 것이 아닌, 스위치를 켜고 스위치로 이동가능한지 여부를 판단해야 하는 문제입니다. 다른 bfs문제처럼 바로바로 큐에 넣는 것이 아닌 여부를 판단하고 큐에 넣어야 하기에 헷갈릴 여지가 있다고 생각합니다. 주의할 점은 (1,1)은 원래 불이 ..
![]()
📕문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 🔎문제설명 모든 사회망 구성원들이 아이디어를 받아들일 수 있게끔 하기 위해 필요한 최소한의 얼리어답터의 개수를 구해야 한다. A가 얼리어답터가 되기 위해서는, A의 친구들이 모두 얼리어답터여야 합니다. 즉 A와 연결된 모든 정점들이 얼리어답터여야합니다. 기본적인 DFS는 리프노드까지 진행한 후 과정을 진행하기에, 리프노드에서부터의 작업을 진행해야 합니다. ..
![]()
📕문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 🔎문제 설명 트리의 지름을 구하는 문제입니다. 여기서 트리의 지름이란 가장 먼 거리의 노드를 쫙 늘려서 원형태로 만들면 가장 먼 노드 2개가 양 끝점으로 지름을 이루는 형태가 될 것입니다. 해당 그림에서는 9와 12를 꼭짓점으로 쫙 늘리면 그 경로의 길이가 트리의 지름이 될 것입니다. 이렇게 우리는 각 노드들 사이의 경로의 길이를 구해서, 그 길이가 최댓값이 되는 경우를..
![]()
문제 https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 🔎문제 설명 K의 사촌을 구하는 문제입니다. 사촌의 정의는 이제 부모가 다르지만, 할아버지, 할머니가 같은 사람들입니다. 부모를 저장하기 위해서 parent 배열을 사용했습니다. parent [idx]는 idx의 부모의 숫자가 저장되어 있습니다. 같은 부모인지 아닌지를 판단하기 위해서는 숫자의 차이를 비교하면 알 수 있습니다. 연속된 입력이 아니라면 다른 부모라는 뜻입..
![]()
문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 🔎문제 설명 단순 구현 문제입니다. 조건이 굉장히 많고요. 하지만 문제를 차근차근 읽고, 경우의 수를 가지치기하면 쉽게 풀 수 있는 문제입니다. 💡주목해야 할 점 학생은 자신을 좋아할 수 없다. 인접한 칸의 정의는 기준칸에서 상하좌우 4방향이다. 자리를 결정하는 규칙이 3가지가 있다. 인접한 칸 내에서 좋아하는 학생이 가장 많은 칸으로 자리를 정합니다. 1번을 만족하는 칸이 여러 ..
![]()
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 설명 문제가 굉장히 길고 복잡해 보입니다. 하지만 주목해야 할 포인트는 아래와 같습니다. 공기청정기의 열은 고정되어 있습니다. 미세먼지는 4방향으로 확산되고, 인접한 방향에 공기청정기나, 칸이 없다면 확산이 일어나지 않습니다. 확산은 기준 칸의 미세먼지양의 5분의 1이 확산됩니다. 공기청정기의 바람은 바람의 방향대로 한칸씩 이동시키고, 시계방향과, 반시계방향이 있습니다. 먼지를 확산시..
![]()
문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니 다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다. S = 3, E = 3인 경우 1은 팰린드롬이다. S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다. 자연수 N개와 질문 M개가 모..
![]()
문제 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다. 출력 첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다. 🔎문제 해석 DP를 기반으로 해서 다른 알고리즘을 병행하면서 해결했다. DP를 통해서 쓸데 없는 연산을 하..
![]()
문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 🔎문제 설명 문제만 보고 이게 DP문제인가? 싶었다. 그냥 무작정 BFS를 사용해서 풀었다. 그랬더니 시간초과가 났다. 이동하는 조건만 맞으면 큐에 넣어줬고, 도착지점에 도착한다면 그게 적절한 이동이라고 생각해서, 결괏값을 계속 더해줘서 함수를 탈출한다면 결과값을 출력해 줬지만 아마 배열 크기도 크고, 큐에 쓸데없는 없는 값이 많이 들어가서 그런 거 같다. 다른 사람들의 풀이를 보니 dfs..
