Future is now

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초 소요) 모든 경우의 수를 찾아보기 위해 순열을 이용하는 브루트포스 알고리..

https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 순열이란 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 합니다. (나무위키 순열 정의 참조) 예를 들어 1 2 3 수들을 순열로 나열해보면, 1 2 3 (오름차순) 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 (내림차순) 이러한 형태가 나타납니다. 여기서 특징은 첫 순열은 항상 오름차순, 마지막 순열을 항상 내림차순 형태를 띄게 됩니다. 또한 부분 순열을 살펴봤을 때에도 부..