[백준/골드3] 1005번 ACM Craft | DP | 파이썬

문제https://www.acmicpc.net/problem/1005서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.위의 예시를 보자.이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다...

• format_list_bulleted 알고리즘/Baekjoon
• · 2025. 9. 30.
• textsms

[백준/실버3] 9095번 1, 2, 3 더하기 | DP | 파이썬

문제https://www.acmicpc.net/problem/9095정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 나의 풀이t = int(input())dp = [0] * 11dp[1] = 1dp[2] = 2dp[3] = 4for i in..

• format_list_bulleted 알고리즘/Baekjoon
• · 2025. 9. 23.
• textsms

[백준/골드4] 2293번 동전 1 | DP | 파이썬

문제https://www.acmicpc.net/problem/2293n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 예제 다른 사람의 풀이n, k = map(int, input().split())coins = [int(in..

• format_list_bulleted 알고리즘/Baekjoon
• · 2025. 9. 16.
• textsms

[프로그래머스/Lv.2] 2 x n 타일링 | 파이썬

문제https://school.programmers.co.kr/learn/courses/30/lessons/12900가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.타일을 가로로 배치 하는 경우타일을 세로로 배치 하는 경우예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항가로의 길이 n은 60,000이하의 자연수 입니다.경우의 수가 많아 질 수 있으므로, 경우의 수를 1,..

• format_list_bulleted 알고리즘/Programmers
• · 2025. 8. 11.
• textsms

[프로그래머스/Lv.2] 땅따먹기 | DP | 파이썬

문제https://school.programmers.co.kr/learn/courses/30/lessons/12913땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.예를 들면,| 1 | 2 | 3 | 5 || 5 | 6 | 7 | 8 || 4 | 3 | 2 | 1 |로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대..

• format_list_bulleted 알고리즘/Programmers
• · 2025. 7. 15.
• textsms

[프로그래머스/Lv.3] 정수 삼각형 | DP | 파이썬

문제https://school.programmers.co.kr/learn/courses/30/lessons/43105위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항삼각형의 높이는 1 이상 500 이하입니다.삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 나의 풀이1 (실패)def solution(tri..

• format_list_bulleted 알고리즘/Programmers
• · 2025. 6. 27.
• textsms

[백준/골드5] 12865번 평범한 배낭 | DP | 파이썬 Python

문제https://www.acmicpc.net/problem/12865이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서..

• format_list_bulleted 알고리즘/Baekjoon
• · 2025. 5. 3.
• textsms

[백준/골드5] 9251번 LCS | DP | 파이썬 Python

문제https://www.acmicpc.net/problem/9251LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 예제 다른 사람의 풀이A = input()B = input()dp = [[0] * (len(B)+1) for _ in range(len(A)+1)]for i in range(1, len(A)+1): ..

• format_list_bulleted 알고리즘/Baekjoon
• · 2025. 5. 2.
• textsms

[백준/골드5] 2565번 전깃줄 | DP | 파이썬 Python

문제https://www.acmicpc.net/problem/2565두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않..

• format_list_bulleted 알고리즘/Baekjoon
• · 2025. 5. 1.
• textsms

[백준/골드4] 11054번 가장 긴 바이토닉 부분 수열 | DP | 파이썬 Python

문제https://www.acmicpc.net/problem/11054수열 S가 어떤 수 Sk를 기준으로 S1 > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입력첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ ..

• format_list_bulleted 알고리즘/Baekjoon
• · 2025. 4. 30.
• textsms