오뚝이개발자

문제 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 생각의 흐름 combinations() 메소드를 이용하여 team1의 조합을 구한 뒤 그에 대응되는 team2의 조합을 구해 각 team의 구성원들의 능력치합 sum1, sum2를 구해 차이를 비교해주면 된다. 단순히 "차이"이므로 abs()를 써주어야 한다. 코드 # BOJ 14889 import itertools import sys n = int(input()) mat = [list(map(int, input..

문제 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 이전에 포스팅한 1, 2, 3 더하기 3과 유사하지만 차이점은 더할 때 같은 숫자가 연속으로 나오는 경우는 가짓수에 포함하지 않는다는 것이다. 그럼 이를 어떻게 구별해내야 하는가? 단순히 생각해보면 된다. 예컨대, 4를 만드는 가짓수를 구한다고 하자. 이 경우 가능한 case는 1, 2, 3을 만드는 case들에 각각 끝에 3, 2, 1을 더해주어서 만들어야 한다. 근데 이 때 주의할 점은 3을 더할때는 1을 만드는 case들 중..

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 dp[i]에 i를 1, 2, 3 더하기로 i를 만들 수 있는 경우의 수를 저장한다. 동적 프로그래밍을 위한 점화식은 dp[i]=dp[i-1] + dp[i-2] + dp[i-3]이 된다. 이처럼 이전의 3항까지만을 더해주는 이유는 1, 2, 3으로 만드는 수이기 때문에 3만큼 작은 수를 만들 수 있는 가짓수를 더해주면 3이라는 수로 그 부족분을 보충해줄 수 있기 때문이다. 코드 # 백준 15988 t = int(input()) dp..

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 생각의 흐름 dp[i]에는 i라는 수를 만들기 위해 필요한 제곱수들의 최소 항의 갯수를 계산해 저장한다. 그 후 j를 1부터 sq..

문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 dp를 이용해 d[i][j]에는 i개를 더해 j가 되는 경우의 수를 저장한다. 그런데 생각을 해보면 d[i][j]=d[i][j-1]+d[i-1][j]라는 걸 알 수 있다. dp를 직접 표로 그려 계산해보면 이해가 좀 더 쉬울 것이다. 코드 # 백준 2225 n, k = list(map(int, input().split())) dp = [[0]*(n+1) for _ in range(k+1)] for i in range(n+1): dp[1][i]=1 for i in range(2, k+1): for j in ..

문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 생각의 흐름 이전에 포스팅한 적이 있는 가장 긴 감소하는 수열과 유사하다. 차이점은 길이 뿐 아니라 수열까지도 출력한다는 것인데 이 때 뒤에서부터 순차적으로 출력해야한다는 것만 유념하면 된다. 코드 # 백준 14002 N = int(input()) arr = list(map(int, inpu..

문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. www.acmicpc.net 생각의 흐름 각 자리에 있는 수를 선택하였을 때 올 수 있는 가장 큰 합을 dp 리스트에 저장한다. 예를 들어, 문제에서 예시로 주어진 arr = [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]의 경우 dp = [1, 10..

문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 생각의 흐름 예컨대, 세 자리 수를 구할 때 끝자리가 2라면 앞의 두자리에 올 수 있는 수는 2보다 작거나 같은 수들 뿐이다. 이러한 생각에 착안하여 앞자리는 두 자리 수 중 끝자리가 2인수+1인수+0인수임을 알 수 있다. 이것이 바로 동적프로그래밍을..