www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 핵심아이디어 bfs와 dp를 적절히 섞어쓰면 되는 문제이다. 예전에 python으로 풀었는데 지금 풀어보려하니 아이디어가 잘 떠오르지 않았다. dp[x][y] 를 x,y좌표까지 도달할때 소모해야 하는 최소 검은방의 개수로 정의하고 bfs를 돌리면된다. 그리고 이때에는 visited를 사용하면 안되는데 그 이유는, 각 방의 최소값을 계속 판단하여 dp값을 업데이트해주어야 하는데, visited으로 초반에 방문처리를 해버..

www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 핵심 아이디어 간단한 bfs문제이다. 적록색약일때와 아닐때를 분기 하여 bfs 큐에 넣는 조건으로 사용하면 된다. 적록색약일때 => B/G는 같은 색으로 취급 아닐때 => 각각 다른 색깔로 취급 'use strict'; const { DH_NOT_SUITABLE_GENERATOR } = require('constants'); const readline = require('readline'); const ..

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 핵심아이디어 전형적인 DFS문제라서 딱히 언급할 것이 없다. 연결된 모든간선에 대해 dfs를 수행하되, 방문처리를 한 노드는 방문하지 않으면 된다. 'use strict'; const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const solut..

www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 핵심 아이디어. 기본적인 최소 스패닝 트리의 크루스칼 알고리즘을 사용하면 된다 추가적인 조건이 있다면 union을 1번 할 수 록 다른 모든 간선에 t만큼 비용이 추가된다. 모든 간선에 같은 값이 추가되므로, edge를 선택하는 순서에는 변화가 생기지 않으므로 비용을 더해줄때 누적된 t값을 추가적으로 더해주기만 하면된다. 'use strict' const readline = require("readline"); c..

www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 핵심아이디어. 최소 스패닝 트리의 크루스칼 알고리즘을 사용하면 된다. 다만, 특별한 점이 있다면 각 노드들이 발전소가 있는 도시와 일반도시로 나누어 진다는 것이다. 일반 도시들은 발전소에서 전기를 끌어와야 하므로, 모든 발전소 도시들의 미리 union으로 묶어놓고 크루스칼/유니온파인드 알고리즘을 사용하면 된다. 'use strict' const readline = re..

문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 핵심 아이디어 이분탐색으로 찾으면된다! 최악의 경우 N,M이 각각 100000개 이므로 일반적인 방법으로는 시간초과가 나기 때문이다. 'use strict..

문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 핵심 아이디어 서로다른 n개의 수를 합쳤더니 s가 되었고, s가 주어진다. 이때 최대 n을 구하면 되는데, 최대 n을 만드려면 최대한 작은 수를 여러번 사용하기만 하면된다. 하지만 서로 다른 자연수여야 하므로, 1부터 1씩 증가해가며 더해주다가 s가 넘어가는 시점에 멈추고 1을 빼주면된다. 예를 들어서 s=200일때 1부터 20까지 차례로 더해보면 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 순으로 증가함을 알 ..