거의 알고리즘 일기장

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이방법 이 문제도 그냥 시뮬레이션 문제다. 그러므로 주의사항을 보고 꼼꼼히만 코딩을 완성하기만 하면 어렵지않다. 한가지만 주의하자 1. 이미 돌렸던 기어는 다시 돌리면 안된다. 재귀문을 짤때 이 부분을 넣어주지 않으면 재귀문이 끝나지 않을 수 있다. 전체코드 #include #include #include #include using namespace std; int Gears[4][8]; v..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이방법 1. 1 방향으로 한번, 2 방향으로 한번 완전탐색을 돌린다. 2. 탐색하며 바꿔야 할것 2.1 옆에 값과 현재 값이 같을때 -> 그냥 통과 2.2 옆에 값과 현재 값이 다를때 2.2.1 옆에 값과 현재 값의 차이가 1이하일때 2.2.1.1 현재 값 > 옆의 값 2.2.1.1.1 visited 에 걸릴때 -> 이 줄은 안됨 2.2.1.1.2 안걸릴때 2.2.1.2 현재 값 < 옆의 값 ...위와 동일 2.2.2..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이방법 이 문제도 조합을 이용하면 매우매우 간단하다. 1. 조합을 이용해서 팀1, 팀2로 나눈다 2. 나눈 팀의 스코어를 계산한다. 3. 절대값(팀1 -팀2)과 저장된 값과 최솟값을 비교한다. 4. 모든 조합이 나올때까지 반복 (만약 지금 저장된 값이 0이면 0보다 최솟값은 없으므로 break해도됨) #include #include #include #define LIMIT 987654321 using namespac..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 주의할점 1. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 2. 나눗셈은 정수 나눗셈으로 몫만 취한다. 풀이방법 c++을 이용한다면 next_permutation함수를 쓰면 간단하다. 나는 c++을 사용하므로 이 방법에 대해서 설명하겠다. 1. 덧셈(0), 뺄셈(1), 곱셈(..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 풀이방법 그냥 주어진 이 조건들을 만족하는 dfs를 만들면된다. 1. 현재 위치를 청소한다. 2. 현재 위치에서 현재 방향을 기준..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net 풀이방법 기본적인 다익스트라 알고리즘을 사용하면 풀린다. 전체코드 #include #include #include #include..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net 풀이방법 그냥 유니온 파인드 알고리즘 이용하면 답 나옴(밑의 url참조) https://kunkunwoo.tistory.com/22 백..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 풀이방법 1. 벽을 세울 조합을 구해서 -> next_permutaion이용 2. 바이러스 퍼지는것 시뮬레이션 -> dfs 시간복잡도 조합..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이방법 일반적인 dp풀이다. 1. dp[i] = max (dp[i], dp[i-1]) 2. dp[i + t[i]] = max (dp[i + t[i]], dp[i]+p[i]) 주의사항 마지막날이 1일동안 일하는 날일수 있으므로 dp[N], dp[N+1] 중에서 큰수를 출력해야함. 전체코드 #include #include #include using namespace std; int dp[16]; int T[16]; int P[16]; int N; void Input() { cin >> N; int t, p; for (int i = 1;..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 풀이방법 이 문제는 그냥 하드코딩해도 된다. board를 돌리고, 대칭시켜 돌리고 하면 8개 종류의 boad모양이 나오는데, 그걸 ..