#문제 17144번: 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net #접근방법 구현, 시뮬레이션 문제이다. 문제에서 제시한 대로 코드를 작성해주면 된다. #풀이 #include #include int arr[55][55]; int temp[55][55]; int xx[4] = {-1,0,1,0}; int yy[4] = {0,1,0,-1}; int main(){ int r,c,t; int air; int ans=0; scanf..
#문제 14938번: 서강그라운드 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net #접근방법 모든 정점에서 모든정점으로 가는 최단경로를 구할 수 있는 최단거리 알고리즘을 사용하여야 한다. 모든 정점에서 모든 정점으로 가는 플로이드 워셜 알고리즘을 사용하여도 되고, 한 정점에서 모든 정점으로 가는 다익스트라 알고리즘을 반복문을 통하여 모든정점에서 출발시켜서 구하여도 된다. 아래 풀이는 다익스트라 알고리즘을 사용하였다. https://rujang.tis..
#문제 11404번: 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net #접근방법 최단거리 알고리즘 중 모든정점에서 모든정점으로 가는 최단거리를 구하는 플로이드 워셜 알고리즘을 사용해야한다. 이 알고리즘은 O(n^3)이라는 시간복잡도가 걸린다. #풀이 #include #define INF 987654321 int arr[105][105]; int main(){ int n,m; int a,b,c; scanf("%d",&n); scanf("..
#문제 1967번: 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #접근방법 트리의 정보를 단방향 노드로 배열에 저장해준다음, 루트부터 아래로 내려가면서 bfs를 이용하여 트리의 지름을 구해주면 된다. #풀이 #include #include #include using namespace std; vector tree[10005]; int ans; int dfs(int x){ int biglen=0; int len..
#문제 2638번: 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net #접근방법 치즈가 두 변 이상이 공기와 접촉할 때 녹는다. 단, 바깥이 치즈로 둘러쌓여있는 공기일 경우에는 접촉하더라도 카운팅이 되지 않는다. 치즈가 녹고 안쪽 공기가 외부 공기와 접촉할 경우에 안쪽 공기를 외부 공기로 변환시켜주면서 치즈가 녹는 경우를 구하면 된다. #풀이 #include #include using namespace std; int arr[1..
#문제 1504번: 특정한 최단 경로 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net #접근방법 이 문제는 최단거리 알고리즘 중에서 다익스트라 알고리즘을 사용하는 문제이다. 비슷한 문제로 https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-1753%EB%B2%88-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-CC [백준] 1753번 : 최..
#문제 2096번: 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net #접근방법 이 문제는 접근방법은 쉬우나, 메모리 제한이 4MB밖에 안된다. 따라서 메모리 초과가 걸리지 않도록 배열의 수를 줄이는 방법을 생각해야한다. #풀이 #메모리 초과가 걸리는 풀이 #include #define max(x,y) (x > y ? x : y) #define min(x,y) (x < y ? x : y) int arr[100005][3]; int max_arr[100..
#문제 17070번: 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net #접근방법 이 문제는 방향성을 고려하여 파이프를 옮길 수 있는지 여부를 파악해서 dfs로 탐색을 해주면 된다. #풀이 #include int arr[20][20]; int n; void dfs(int x, int y, int direction){ arr[x][y]++; if(direction==0 || direction==2){ if(y
#문제 15686번: 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net #접근방법 이 문제는 모든 경우의 수를 구하는 브루트포스 유형의 문제이다. 브루트포스 알고리즘은 모든 경우의 수를 구하는 알고리즘이다. 비슷한 알고리즘인 백트래킹이 있는데 백트래킹 알고리즘은 모든 경우의 수를 찾을 때, 필요없는 부분은 가지치기하면서 구하는 알고리즘이다. #풀이 #include int house[105][2],hnum; int ..
