다이나믹프로그래밍9

• 

  [BOJ] 11727 2xn타일링 2 - JAVA 1. 문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 2. 풀이 규칙 변형된 2xn타일링 문제다. N=2일때의 경우의 수가 한 개 늘어남에 따라 나머지 경우의 수들도 전부 영향을 받았다. N을 N-1의 경우의 수+ N-2의 경우의 수로 표현하는 골격은 비슷하지만 N-2의 앞에 붙일 수 있는 게 두 가지라 2*(N-2경.. 코딩테스트/BOJ 2022. 3. 22.

• 

  [BOJ] 11726 2xn 타일링 - JAVA 1. 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 2. 풀이 규칙 결론부터 얘기하면 피보나치다. N을 N-1, N-2부분으로 나눠서 생각하면 쉽다. 항상 앞에 1칸 세로 또는 2칸 가로가 붙는다고 생각하면 된다. 코드 dp배열 크기를 가변적으로(N+1)정해줬으므로 N 코딩테스트/BOJ 2022. 3. 19.

• 

  [BOJ] 9095 1, 2, 3더하기 - JAVA 1. 문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 이 문제 설명이 좀 이상하다. n을 1,2,3의 합이 아니라 1,2,3 조합으로 설명해야 차라리 명확할 것 같다. 문제만 보면 2는 1+1만 되고 2는 안될 것 같은데 2도 된다. 1 --> 1 2 --> 1+1, 2 3 --> 1+1+1, 2+1, 1+2, 3 4 --> 1+1+1+1, 1+3, 1+1+2, 1+2+1, 2+2, 2+1+1, 3+1 n --> 1+(n-1), 2+.. 코딩테스트/BOJ 2022. 3. 17.

• 

  [BOJ] 1912 연속합 - JAVA 1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 2. 풀이 (이전값 최대+현재 값)과 현재 값을 비교해서 .. 코딩테스트/BOJ 2022. 3. 15.

• 

  [BOJ] 2156 포도주 시식 - JAVA 1. 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 .. 코딩테스트/BOJ 2022. 3. 15.

• 

  [BOJ] 17070 파이프 옮기기 1 - JAVA 1. 문제 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회.. 코딩테스트/BOJ 2022. 3. 15.

• 

  [BOJ] 2579 계단 오르기 - JAVA 1. 문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나.. 코딩테스트/BOJ 2022. 3. 12.

• 

  [BOJ] 10844 쉬운 계단 수 - JAVA 1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 2. 풀이 규칙 최선을 다해 그려봤다.ㅋㅋㅋ N=1일때, 0빼고 1~9까지 한번씩 모두 가능하다. 그래서 N=1일때 계단수는 9다. N=2일때, 각 숫자는 자신의 양 옆에 있는 숫자값을 더해서 구할 수 있다. 예를 들면, N=1인 숫자 중 5는 N=2가 됐을 때 다음 수로 4와 6 중에 선택할.. 코딩테스트/BOJ 2022. 3. 12.

• 

  [BOJ] 9461 파도반 수열 - JAVA 1. 문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5.. 코딩테스트/BOJ 2022. 3. 9.