[백준 / C++] 11057번: 오르막 수 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 이어지는 숫자는 각 자리의 숫자보다 크거나 같아야 한다. 따라서 다음과 같은 규칙을 발견할 수 있다. 0으로 끝나려면 앞의 숫자는 0이어야 한다. 1로 끝나려면 앞의 숫자는 0 또는 1이어야 한다. 2로 끝나려면 앞의 숫자는 0 또는 1 또는 2여야 한다. ... 이를 점화..

• format_list_bulleted PS/백준
• · 2023. 7. 26.
• textsms

[백준 / C++] 1932번: 정수 삼각형 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 맨 윗 칸부터 아래로 내려가면서 선택한 수의 합이 최대가 되어야 한다 arr[i][j]를 선택할 때, arr[i-1][j-1] 와 arr[i-1][j]를 선택했을 때 중 합이 더 큰 걸 골라야 한다 #include using namespace std; int previ[501], pres[501]; int main() { ios::sync_with_stdio(0); cin.tie(..

• format_list_bulleted PS/백준
• · 2023. 7. 16.
• textsms

[백준 / C언어] 17070번: 파이프 옮기기 1 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍 (dp), 그래프 탐색 (DFS) 접근 방법 각 칸 별로 옮길 수 있는 방법의 수가 정해져 있으므로 dp를 이용해 풀어야겠다고 생각했다. 파이프를 옮겼을 때 가로 상태이려면 이전 상태가 가로 또는 대각선 상태여야 한다. 그리고 대각선 상태라면 이전 상태가 가로 또는 대각선 또는 세로 상태여야 하고, 세로..

• format_list_bulleted PS/백준
• · 2023. 6. 30.
• textsms

[백준 / C언어] 9184번: 신나는 함수 실행

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 난이도: solved.ac 실버 2 알고리즘 분류 다이나믹 프로그래밍 (dp) 구현 배열의 index는 0부터 시작하므로 50을 더해 0부터 100까지의 index를 가진 3차원 배열 dp를 만들어주었다 문제에서 주어진 pseudo 코드를 그대로 옮기면 안된다 나는 두 번째 if문을 따로 처리해주었다 (이유: pseudo 코드의 순서대로 진행하면 w(20,20,20)이 만들어지지 않았는데 w(20,2..

• format_list_bulleted PS/백준
• · 2023. 6. 26.
• textsms

[백준 / C언어] 1309번: 동물원 (dp)

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 이 문제에서 중요한 부분은 가로 또는 세로로 붙여서 배치시킬 수 없다는 것이다 따라서, 사자를 배치하는 경우는 아래 세 가지로 나눌 수 있다 1) 이전 칸에서 왼쪽에 배치한 경우 2) 이전 칸에서 오른쪽에 배치한 경우 3) 이전 칸 둘 다 배치하지 않은 경우 1번의 경우에는 이전에 왼쪽에 배치되어 있으므로 왼쪽에 또 배치시킬 수 없다 따라서 오른쪽 칸에 배치시키거나 아예 둘 다 비워놓는 경우만 가능하다 2번의 경우에는 이전에 오른쪽에 배치되어..

• format_list_bulleted PS/백준
• · 2023. 6. 25.
• textsms

[백준 / C언어] 1010번: 다리 놓기

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 난이도: solved.ac 실버 5 사용 알고리즘 조합 접근 방법 조합을 활용한 문제다 다리를 놓는다는 것은 강 동쪽의 사이트 M개에서 강 서쪽의 사이트 N개로 선을 잇는다는 것인데, 이는 곧 M개에서 N개를 선택하는 경우를 말한다 경우의 수를 구하는 문제이므로 순열 또는 조합을 이용해야 할 텐데 여기서 순열이 아니고 조합인 이유는 바로 강 동쪽의 사이트에서 강 서쪽의 사이트로 다리를 놓는데 다리..

• format_list_bulleted PS/백준
• · 2023. 5. 26.
• textsms