풀이 보관함

🔗 문제 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 출력 첫째 줄에 사각 지대의 최소 크기를 출력한다. ✏️ 풀이 먼저 문제 정리 부터 한다. [맵이 가질 수 있는 상태] EMPTY : ..

🔗 문제 2636번: 치즈 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net N, M ≤ 100 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게..

🔗 문제 2467번: 용액 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net ✏️ 풀이 문제에서 보아야 할 것은 이미 용액이 "정렬된 상태 "인 것이다. 더 해야 할 용액도 2개다 싶어서 투포인터를 떠올렸다. 양 끝을 start, end라는 변수로 가리키며 그 합을 sum에 저장해 주었다. 이때 값은 오름차순 정렬이므로 start는 가장 작은 값(0 위치), end는 가장 큰 값 (N-1 위치)을 가리킨다. 만약 sum이 0이라면 더 이상 진행할 필요가 없다. 만약 sum < 0 이라면 작은 값을 가리키는..

🔗 문제 21609번: 상어 중학교 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 🖍 풀이 6달전에 푼거보다 개선되어서 다시 올리는 풀이 ✌🏻 문제를 읽고 코드 흐름을 간단하게 정리해보자. while(flag) { //1. 블럭 그룹들 찾기 //2. 조건에 맞는 블럭 제거하고 점수 얻기 // => 블럭 없으면 종료 flag = false //3. 아래로 중력 작용 //4. 반 시계 방향으로 회전 //4. 아래로 중력 작용 } 조건 정리 ✔️ 맵의 상태는 3가지의 블럭 종류와 빈 칸으로 이루어진다. enum..

🔗 문제 23290번: 마법사 상어와 복제 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net ✏️ 풀이 일단 이 문제는 내가 무려 밍기적 거리는 시간 포함해서 2주 동안 못 풀고 있던 것입니다. 이유는 예제 4, 5, 8에서 오답이 나와서, 다음은 예제 5번이 안 나와서. 총 2번의 대수정을 거쳐서 메모리 2028KB, 0ms로 문제로 맞았습니다!! 를 보게 됐다. 풀이 안 쓰려고 했는데 나한테도 도움될 것 같아서 오랜만에 자세히 써보고자 한다.. 문제를 읽으면 알겠지만, 간단하..

🔗 문제 https://softeer.ai/practice/info.do?idx=1&eid=582 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai ✏️ 풀이 다익스트라 문제다. (1) 출발 지점이 주어져있고, (2) 양방향이며, (3) 가중치가 양수다. 무엇보다 출발 지점에서 특정지점까지 필요한 값을 출력해야한다는게 다익스트라문제라는 큰 힌트다. 다익스트라를 학습할 때 주로 사용하는 최소 경로가 아니라 최소 레벨을 구해야하는게 작은 차이일 뿐이다. 정석 다익스트라 풀이로 priority_queue를 이용했다. dp[node]에 1에서 node까지 가는 가장 큰 레벨을 저장한다. 문제의 제약조건을 보면 총 노드의 수는 $2 ≤ N ≤ 10,000$ 로 한정되어 있다. 가..

🔗 문제 11404번: 플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ✍️ 풀이 제목부터 거저주는 플로이드 기초 문제 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 플로이드 와샬이다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 그렇다면 A→B 중 가장 작은 비용 값을 저장하자. 💾 소스 #include #include #include const int INF = 1e9; std::vector adj; int N..

🔗 문제 1389번: 케빈 베이컨의 6단계 법칙 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net ✍️ 풀이 무방향 그래프에서 모든 정점의 최단 경로를 구해야 한다? 플로이드 와샬 문제였다. 주의 사항 무방향 그래프이므로 a→b면 b→a임을 잊지 말자. 플로이드 와샬이 방문하지 않은 인접행렬의 초기값은 INF이지만 이 문제에서 자기 자신으로 가는 값은 0으로 설정하는 것에 유의해야 한다. 출발노드가 중간노드나 목적지가 되는건 찾을 필요가 없다. 💾 소스 #incl..

🔗 문제 1956번: 운동 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net ✍️ 풀이 방향 그래프로 표현되는 경로에, 두 정점의 최단 거리를 구한다? 플루이드 와샬을 이용해서 푼다. 그래프가 주어졌을 때 두 정점의 최단 거리를 구할 때 사용한다. 그래프를 인접 행렬로 표현하며, 아직 경로를 찾지 못한 곳은 INF이다. 플루이드 와샬의 핵심은 a→b로 이동하고자 할때 중간 노드를 고려한다는 점이다. O(V^3)의 시간이 걸리지만 v가 400으로 작은 축에 속해서 문제를 풀 수 ..

🔗 문제 1949번: 우수 마을 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net ✍️풀이 문제를 읽어보면 트리 구조의 마을에 정점에 가중치가 주어진다. 마을은 인접한 마을끼리 우수마을이 될 수 없으며, 우수 마을이 아닌 곳은 적어도 하나의 우수 마을과 인접해야 한다. 어떤 노드를 선택했을 때, 그 마을을 우수 마을로 하느냐 하지 않느냐에 따라서 어떤 합이 나올지 몰라 계산이 필요한 식이다. 그냥 여기서 dp가 떠올랐다. 하지만 .. 어떻게 문제를 풀지는 감이 잡히지 않아서 인터넷의 도움을..