Future is now

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 주어진 지도에서 1이 들어있는 칸끼리 연결한 것을 모양이라고 하는데, 지도의 칸에 들어있는 수를 변경해서 모양의 최대 크기를 구하는 문제입니다. 지도는 0, 1로만 구성되어 있는데요. 1을 0으로 바꾸면 모양의 크기는 무조건 줄어들기 때문에 0에서 1로 바꿔는 쪽으로만 생각합니다. 단순히 생각해서 한 칸씩 바뀔 때마다 그룹의 최대 크기를 구해본다고 했을 때, 시간복잡도는 \(O(NM*N..

https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 돌 그룹 3가지가 있는데 이 3가지 그룹의 돌 개수를 같게 할 수 있는지를 찾는 문제입니다. 각 그룹의 돌 개수를 정점이라고 생각하면 BFS로 풀 수 있습니다. 점화식은 d[a][b][c]로 정할 수 있는데, 전체 돌 개수를 구한 sum = a + b + c 값을 이용하면 굳이 3차원 배열이 아닌 d[a][b]인 2차원 배열으로도 문제를 해결 할 수 있습니다. 점화식 d[i][j] : 첫 번..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 건물 층을 엘리베이터로 방문하는데 목적층에 도달하기 위해 엘리베이터 버튼을 적어도 몇 번 눌러야 하는지 구하는 문제입니다. 적어도라는 말은 최소로 버튼을 눌러보는 것으로 바꿔서 생각할 수 있습니다. 최소로 버튼을 눌러서 각 층을 방문한다고 생각할 수 있는데 각 층을 정점이라고 생각해 보면, BFS로 문제를 해결하면 되겠습니다. 각 층에 방문할 때 dist 배열에는 최소로 버튼을 누르는 횟수를 저장하면서, 동시..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색(knapsack) 문제로도 유명한 다이나믹 문제입니다. 문제에서 배낭에 넣을 수 있는 무게 k가 주어지고, n개의 물건은 각각 무게 w와 가치 v가 주어집니다. 배낭 안에 물건을 이리저리 넣었을 때 담을 수 있는 물건의 최대가치값을 구하는 것입니다. n개의 물건 각각은 배낭 안에 들어가거나 안 들어갈 수 있으며, 동일한 물건은..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 수빈이가 동생 위치에 도달하기까지 주어진 조건을 만족하며 최소로 걸리는 시간을 구하는 문제입니다. 수빈이의 현재 위치를 x라고 할 때, 움직일 수 있는 행동으로는 1. 순간이동 x → 2 * x (소요시간:0초) 2. 앞으로 이동 x → x + 1 (소요시간:1초) 3. 뒤로 이동 x → x - 1 (소요시간:2초) 이렇게 3가지 입니다. 우선, 수빈이의 처음 시..

https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net unsigned long long 으로 선언하더라도 저장할 수 없는 큰 수의 연산 문제입니다. 문제의 조건에서 주어지는 수들은 양수이기 때문에 음수의 경우는 신경쓰지 않아도 됩니다. 주어진 수의 값은 최대 \(10^{10000}\)입니다. 1뒤에 0이 1만개가 붙습니다. 수를 string으로 입력 받고, int형 배열로 저장한 후 각 자리수 마다 덧셈 처리를 합니다. 주의해야 할 부분은 같은 자리수의 덧셈시 9보다 커지는 경우 자리올림수 처리 입니다. int carring = 0; 이라는 변수를 선언하여 ..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제에서 주어진 수열의 순서는 변경이 없고, 주어진 연산자들의 순서만 바꿀 수 있습니다. 또한 연산사 우선순위를 따지지 않고 앞에서부터 계산하는데, 그때 가능한 최대값과 최소값을 구하는 문제입니다. 연산자를 +, -, *, / 의 순서대로 배열에 저장합니다. 배열에 저장할 때는 덧셈부터 차례대로 0, 1, 2, 3이 되며, 덧셈이 두개라면 0..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 이번 로또 문제는 주어진 k개의 수들 중에 6개의 수를 골라서 출력하는 문제입니다. k가 8이라고 했을 때 k개 중에 6개를 고른다는 것은 k개 중에 2개를 고르는 것과 같습니다. 골랐다는 의미를 1이라고 하고, 고르지 않았음을 0이라고 했을 때, 골라야 하는 수의 개수는 6개이므로 고르지 않은 수는 k-6개입니다. 새로운 순열을 하나 만드는데, 0을 k-6개, 1을 6개 넣은 배열을 ..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 유명한 문제 중 하나입니다. 모든 도시를 거쳐가는 순서들 중 가장 적은 비용을 들이는 외판원의 순회 경로를 구하는 것인데요. 한번 갔던 도시로는 다시 갈 수 없고, 모든 도시를 거친 후 다시 원래의 도시로 돌아와야 합니다. 세부 문제 내용은 위 링크..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 배열에 들어있는 정수의 순서를 적절히 바꿔서 문제에서 주어진 식의 최대값을 구해야 합니다. 수의 개수 제한이 N (3 ≤ N ≤ 8) 이므로 최대 8개의 수를 일렬로 나열하는 경우의 수는 \(8!\)이 됩니다. \(8! = 40,320\)가지이므로 4만여정도는 모든 경우의 수를 다 계산해보아도 무리가 없습니다. (1억가지의 수가 대략 1초 소요) 모든 경우의 수를 찾아보기 위해 순열을 이용하는 브루트포스 알고리..