본문 바로가기

acmicpc

[백준][Python][2225][DP] 합분해 문제 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 배열의 의미는 다음과 같다 세로 K = K개의 숫자를 쓴다 가로 N = 0-n 까지를 써서 만든다. 이랬을 때, 문제 조건상 1개의 숫자로 만들수 있는 n 후보들의 갯수는 1이다. 0을 0번써서 만드는 건 1로 하자. 이때, i개를 써서 j를 만드는 방법의 갯수는 (i-1개를 써서 0-j 까지를 만드는 방법의 갯수의 총 합) 으로 나타낼 수 있다. 왜냐면, 10 = 9를 만드는 방법의 수 + 1, 8을 만드는 방법의 수 +2 ... 이런 식으로 나타낼 수 있기 때문이다. 원래는 10을 만드는 방법의 .. 더보기
[백준][Python][17404][DP] RGB거리 2 문제 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net DP 문제인데 정말 어려웠다. 이 문제는 RGB거리 와 비슷한데, 마지막 집과 첫번째 집이 인접한 원형 형태로 구성되어 있다고 한다. 그래서 마지막 답을 구할때, 첫번째에 어떤 집을 .. 더보기
[백준][11052번, 16194번][Python] 카드 구매하기 1,2 && 블로그 닉값의 위험성 주의! 이 문제는 블로그 닉네임 값을 한 문제이며 닉값하지 말자는 반성문입니다. 두 문제의 차이는 간단하다. 최대를 구하냐, 최소를 구하냐 정도뿐이다. dp문제에서 dp배열을 초기화할때는 (나는) 값을 0으로 한다. 별 의미도 모르는채로 초기화한다. 방법은 다음과 같다. dp[n] = n개의 카드를 샀을때의 최댓값, 최솟값을 구한다. for i in range(1,n+1): for j in range(1,i+1): dp[i] = max(dp[i], dp[i-j]+arr[j]) 이때, 이 문제는 i 개의 카드를 살때 최댓값을 구하는 첫번째 반복문과, 1 16149 은 i번째 까지 샀을때는 == j번째 카드팩을 샀을때 값이 최대/최소가 될까? 를 판별하는 식이다. 이건 간단한데, 여기서 닉값을 했다가 시간을.. 더보기
[백준][9095][Python][DP] 1,2,3 더하기 문제 : 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 간단한 DP 문제다. 1,2,3 더하기 시리즈 문제를 보면, 여러 제약조건이 생기면서 (같은 번호 2개이상 붙이면 안.. 더보기
[백준][Python][10971][브루트포스] 외판원 순회 2 문제 : 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 는 유명한 NP-Complete 문제다. O(N!)의 어마어마한 복잡도를 가지는 문제이므로 순열도 부담없이 사용했다. 문제 풀이는 다음과 같다. 1-n 사이의 모든 순열을 만든다. 수열 하나하나마다: 1-2.. 더보기
[백준][Python][11057][DP] 오르막 수 문제 : https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 이 문제는 고생 많이한 문제다. 문제의 해결법은 다음과 같다. d[i] 를 i+1 번째 자릿수의 앞자리 로 하자. 1자리 숫자들은 전부 오르막 수로 볼수 있기 때문에 1로 초기화한다. 이제 생각해보면 12,13,14.. 23,24,25..등등은 전.. 더보기

티스토리툴바