본문 바로가기
반응형

dp56

(Python/🥈3)백준 알고리즘 1003번: 피보나치 함수 문제 바로가기 문제: int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다 fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 0을 출력하고, 0을 리턴한다. fibonac.. 2023. 6. 29.
(Python/🥈3)백준 알고리즘 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보다 작다. 출력: 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. import sys sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r') T = int(sy.. 2023. 6. 28.
(Python/🥇4)백준알고리즘 12865번: 평범한 배낭 문제 바로가기 문제: 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.  입력: 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K .. 2023. 6. 13.
(Python/🥈1)백준 알고리즘 2156번: 포도주 시식 계단 오르기 바로가기 문제 : 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을.. 2023. 6. 12.
(Python/🥈4)백준 알고리즘 10844번: 쉬운 계단수 문제 바로가기 문제: 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력: 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력: 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 처음에 문제를 이해하지 못했다. N만큼의 간격을 유지한다는줄 알았지만. 하다보니 길이가 N이다 1이면 일의자리 2이면 십의자리 ,,, 이차원 리스트를 사용하여 dp를 늘려야한다. 근데 차이가 1이 나야하니깐 1과 9 빼고는 (-1,+1) 로 갈수 있고 1과 9 는 0과 8 밖에 못간다. 그 외는 위 아래.. 2023. 6. 12.
(Python/🥈4)백준 알고리즘 1463번: 1로 만들기 문제 바로가기 문제: 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력: 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력: 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 : 이 문제는 dp 를 사용하는 문제이다. 나는 포문을 이용한 바텀업 방식이 더 익숙하고 처음 두 수를 알수 있어 상향식인 바텀업으로 풀었다 처음에는 그리디를 생각할 수 있지만 10인경우에 -1 을 먼저 하는 경우가 유리하기 때문에 불가능하다. 점.. 2023. 6. 12.
반응형

티스토리툴바