오뚝이개발자

문제 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,3,4를 넘버링하여 각 연산자의 갯수만큼 리스트에 채운다. 이들의 순열을 이용하여 가능한 모든 연산의 경우의 수를 구한다. 비교하며 최솟값, 최댓값을 찾는다. 코드 from itertools import permutations N = int(input..

문제 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 생각의 흐름 n개의 도시들을 1부터 n까지 넘버링하여 리스트에 삽입한다. 도시 리스트를 next_permutation() 함수를 이용해 가능한 모든 순열마다 input으로 주어진 weight 정보를 이용해 cost를 계산해 비교한다.(브루트포스) 이 때, weight가 ..

문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 생각의 흐름 이전에 포스팅했던 모든순열의 로직을 이용해 가능한 모든 순열에 대해 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|의 값을 구한다. 주의할 점은 중복된 원소(즉, 같은 수)가 있을 수 있으므로 비교 시에 등호를 넣어주어야 한다. 위 식의 최댓값을 찾는다. 코드 def next_permutation(arr): n = len(arr)-1 i = ..

문제 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 생각의 흐름 처음에 리스트를 1부터 넣어 초기화해주고 이전에 포스팅했던 다음 순열의 알고리즘을 사용하면 된다 코드 def next_permutation(arr): n = len(arr)-1 if n==0: return -1 i = n while arr[i-1] > arr[i]: i -= 1 if i == 0: return -1 j = i-1 diff = 10000 position_to_switch = 0 for k in range(i, n+1): if arr[k]-arr[j] > ..

문제 https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 생각의 흐름 다음 순열 문제의 대소비교 부분을 반대로 생각하면 된다. 코드 def next_permutation(arr): n = len(arr)-1 if n==0: return -1 i = n while arr[i-1] < arr[i]: i -= 1 if i == 0: return -1 j = i-1 diff = -10000 position_to_switch = 0 for k in range(i, n+1): if arr[k]-arr[j] < 0:..

문제 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 생각의 흐름 다음 순열을 어떻게 찾아낼까? (규칙성) 일의 자리부터 시작하여 바로 앞의 수보다 큰지 작은지를 비교하여 판별한다. 깨달은 점 사실 파이썬에는 이러한 기능을 구현해주는 permutations라는 아주 편리한 라이브러리가 있다...하지만, 구현을 해보는 데에 의의가 있으니^^ 코드 def next_permutation(arr): n = len(arr)-1 if n==0: return -1 i = n while arr[i-1] > arr[i]..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 생각의 흐름 맨 마지막으로 더하는 수가 각각 1,2,3인 경우로 나누면 dp를 사용해야 함을 알 수 있다. dp[i] =..

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 생각의 흐름 최댓값을 구하기 위해 필요한 규칙성이 없음을 발견 -> 즉, 브루트포스로 모든 경우를 계산해봐야 함 모든 경우란 ..