본문 바로가기

백준/동적프로그래밍49

백준 5557 c++ "1학년" -PlusUltraCode- https://www.acmicpc.net/problem/5557 [필자 사고]이 문제는 배낭 문제와 유사하다.바깥 반복문에는 몇번째 숫자들의 경우의수로 반복문을 설계하고안쪽 반복문에는 0~20까지의 숫자들의 모든 경우의 수를 구해줘야 된다. 필자는 dp 배열식을 dp[i][k] 라고 설정할 때 i번째 수에서 k라는 값의 경우의 수를 dp라고 설정했다. 이 문제만의 매력은 0~20이라는 범위를 줘서 배낭문제 알고리즘을 이용하여 풀라는 힌트를 주었고특정 어떤 값은 이전 i번째 값의 갯수를 기존값에 더하는 형태로 갱신해주는 경우이다. 필자는 이 부분에서 갱신 작업을 틀렸다. 덧셈이 2번일어나면 2를 곱한것과 같다..  아래는 상세한 코드 해설이다.[코드 해설]1. 입력 처리 (Input 함수)Input() .. 2025. 3. 4.
백준 9084 c++ "동전" -PlusUltraCode- https://www.acmicpc.net/problem/9084  [필자 사고]배낭문제를 응용한 문제이다.이 문제를 풀면서 새로운 사고를 얻었다. 바깥 반복문은 동전 종류 수만큼 반복문을 돌리고안쪽 반복문은 동전을 시작점으로 받아서 하나하나 갯수를 갱신해주는 방식이다. 여기서 실수한 부분은 매번 갱신한다는 의미는 값을 덮어쓰는게 아닌 이전 값과 더해주는 연산을 해줘야 된다. 새로운 사고를 얻을 수 있는 문제라서 좋았다.아래는 자세한 코드 해설이다.[코드 해설]1. 입력 처리 (Input 함수)Input() 함수는 테스트 케이스마다 필요한 데이터를 입력받고 초기화하는 역할을 합니다.N (사용 가능한 동전의 개수)을 입력받습니다.동전의 금액을 입력받아 coin 벡터에 저장합니다.totalMoney (만들어.. 2025. 3. 4.
백준 2096 c++ "내려가기" -PlusUltraCode- https://www.acmicpc.net/problem/2096 [필자 사고]처음에 필자는 N의 크기에 따라 열의 크기도 변하는 줄 알았다.정답은 당연히 틀렸다.두번째로 행의 크기만 변한다는걸 알고 열의 크기는 3으로 고정하고 2차원 배열 형태로 풀었따.다만 메모리 초과 문제를 마지했다.생각해보니 이전 값들은 필요가 없다. 현재가 중요하다.그래서 maxDp, minDp 등등을 2차원 배열에서 1차원배열로 만들고 크기를 3으로 했다.그런데 또 메모리 초과 문제를 맞이했다.... 입력 배열 또한 2차원으로 되어있어 1차원으로 줄였떠니 문제를 해결할 수 있었다.메모리에 대해서 깊이 고민해 봤던 문제다.아래는 자세한 코드 해설이다.[코드 해설]2. 입력 처리 (Input 함수)cpp복사편집void Input(.. 2025. 3. 2.
백준 2565 c++ "전깃줄" -PlusUltraCode- https://www.acmicpc.net/problem/2565 [필자 사고]LIS알고리즘을 떠올릴수 있으면 해결 point를 얻을 수 있었을 것이다.있다가 나오는 index i의 의미는 i번째 이전에 있는 값들 중 자신보다 뒤에 있는 숫자들은 몇개인가?? 를 묻는 문제이다.그래서 LIS문제는 매번 resultCount를 이용해 최대값을 갱싢해 줘야된다. 필자는 이 부분을 놓쳤다. 마지막 결과물에서 N-resultCount를 하면 답을 구할 수 있을 것이다. 아래는 상세한 코드해설이다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 프로그램에서 사용할 데이터를 입력받고 초기화하는 역할을 한다.먼저, N을 입력받아 주어진 데이터의 개수를 설정한다.dp 벡터와 arr 벡터를 크기 N+1.. 2025. 2. 28.

티스토리툴바