Algorithms63 백준 10844. 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 점화식을 잘 세워야 한다는 것을 명심한 문제.. i가 숫자열의 길이라고 했을 때, 맨 뒤에 올 수 있는 수의 갯수는 다음과 같다. 이전 i의 대각선의 합으로 나타나는 것으로 알 수 있다. 좌우 끝(1, 9)의 경우에는 대각선 하나의 합으로 나타나고. 따라서 점화식을 코드로 구현하면 다음과 같다. n = int(input()) dp = [[0 for _ in range(10)] for _ in range(101)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, n.. 2022. 7. 1. 백준 1463. 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적 프로그래밍은 뭔가 감 잡은 것 같다 하면 또 신기한 문제가 튀어나오네.. 기본적으로 작은 값부터 쌓아올리는 시도는 했는데 카운트 자체를 셀 생각이 쉽게 나지 않았다. n = int(input()) d = [0] * (n + 1) for i in range(2, n+1): d[i] = d[i-1] + 1 #1을 뺀 경우는 d[i-1]연산 + 1번 연산 if i%3 == 0: d[i] = min(d[i], d[i//3] + 1) #더 작은 게 필요하기 때문에 1을 빼는 연산과 나머지 연산 비교 if i%2 =.. 2022. 6. 30. 백준 2579. 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이런 문제에서 절실히 느끼는 것.. 조그만 문제부터 해결하고 이를 이용해서 답을 도출하자 3개의 계단이 있다고 할 때 구해보면, 1->3 혹은 2->3이 문제의 해결책이 된다. 이 중에서 가장 큰 값을 구하면 됨. 4개의 계단이 있다고 하면, 두 가지 경우의 수로 나뉜다. 3을 밟고 4를 밟거나, 2를 밟고 4를 밟거나. 따라서 계단이 1, 2, ... 일 경우 최댓값을 구하고, 3을 밟았을 때 최댓값 + 4.. 2022. 6. 29. 백준 1932. 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 합이 최대가 되도록 삼각형의 구성요소를 한 행당 하나씩 뽑아 구성하면 된다. 다만 이 때, 아래층에 있는 수는 왼쪽 혹은 오른쪽 위 대각선에 있는 요소만 선택할 수 있다. 단순히 위에서부터 내려오면서 합을 누적시켜 구할 수 있는데, 이 때 양쪽 끝 요소의 경우 오른쪽 대각선 혹은 왼쪽 대각선 요소가 당연히 선택되므로 이에 따른 처리를 해주고, 중간에 낀 요소들은 좌우 대각선 요소를 비교해서 더 큰 값을 넣어주면 된다. 그 후 마지막 행에서 가장 큰 요소를 찾아주면 된다.. 2022. 6. 28. 이전 1 2 3 4 5 6 ··· 16 다음
