[백준 / C++] 2193번: 이친수 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 0은 여러개 이어져도 상관없다. 1은 2개 이상 연속되면 안 된다. 따라서 0 이전의 숫자는 0 또는 1이 가능하고, 1 이전의 숫자는 0만 가능하다. 그럼 점화식은 아래와 같이 나타낼 수 있다. n번째 숫자가 0인 경우의 수: dp[n][0] = dp[n-1][0] + dp[n-1][1] n번째 ..

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

[백준 / 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++] 7569번: 토마토 (BFS, 3차원 배열)

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 난이도: solved.ac 골드 5 box라는 3차원 배열을 만들고, 해당 배열에 입력을 받았다. 그리고 먼저 box[i][j][k] = 1인 곳을 큐에 담고, 큐에서 하나씩 꺼내 주위 위, 아래, 오른쪽, 왼쪽, 앞, 뒤 중 0인 곳은 값을 1씩 증가시켜 저장하였다. 0일차를 1로 시작했으므로 box[i][j][k]가 가장 큰 곳에서 1을 뺀 값을 출력하도록 해주었다. 그..

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

[백준 / C++] 5430번: AC

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 난이도: solved.ac 골드 5 일단 수를 배열에 저장시키고, front와 rear라는 커서를 둬서 R이면 front와 rear의 위치를 서로 바꾸고 D면 front를 한 칸 이동시키는 식으로 풀었다 그리고 front와 rear 사이에 수가 없는데 D를 하면 error를 출력하도록 해주었다 수를 배열에 담을 때는 '['와 ']'를 따로 입력받고, 수는 콤마(,)로 구분해서 입력받았다 #define _CRT_SECURE_NO_WARNINGS #incl..

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

[백준 / C++] 1764번: 듣보잡 (정렬 문제)

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 일단 듣도 못한 사람 (hear)과 보도 못한 사람 (see)를 입력받고 각각 정렬시킨다 그 후 merge sort에서 merge할 때처럼 정렬된 두 개의 배열에 커서를 두고 각각의 커서가 가리키는 같으면 배열 ans에 넣어주었다. 커서가 가리키는 이름 서로 다를 때는 사전순으로 더 앞선 쪽의 커서를 1칸 이동시킨다. #include using namespace std; int main() { ..

• format_list_bulleted PS/백준
• · 2023. 7. 16.
• 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