본문 바로가기

백준/동적프로그래밍51

백준 2240 c++ "자두나무" -PlusUltraCode- https://www.acmicpc.net/problem/2240 [필자 사고]이 문제는 동적프로그래밍 문제이다.이 문제를 풀면서 확실히 동적프로그래밍에서 배열의 인덱스를 대하는 자세는 기존 배열 형태보다는flag느낌으로 사용해야 된다는걸 다시 한번 느꼈다.처음 배열에서는 time 두번째 배열은 pos 세번째 배열은 위치 이동 가능한 숫자 형태로 flag 형식으로 배열들을 선언하고해당 조건들이 성공될 때 데이터를 업데이트 해주는 식으로 문제를 해결했다.2차원에서 3차원으로 바꼇을 뿐인데 기존 고려할게 더 많아졌다. 아래는 자세한 소스코드 해설이다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 게임의 기본 정보를 입력받아 초기화하는 역할을 한다.T, W를 입력받아 각각 총 시간과 이동.. 2025. 3. 6.
백준 15989 c++ "1, 2, 3 더하기 4" -PlusUltraCode- https://www.acmicpc.net/problem/15989 [필자 사고]늘 더하기 문제는 숫자들의 순서가 상관이 있었다. 다만 이 문제만의 특별한 점은 순서가 상관이 없다.즉 필자는 몰랐던 개념을 배웠다.오름차순 느낌으로 점화식을 설계해야 된다.dp[i][k] i번째 수는 k이하의 수로 완성한다. 즉 dp[i][k] = dp[i-k][k--] 이런식으로 값을 덮어 씌어야 된다. 이전에 순서가 상관이 있을 때는 값을 += 형태로 더해나가는 동적 프로그래밍이다.위와 같은 논리를 이해하게 되면 문제를 풀 수 있다.아래는 자세한 코드 해설입니다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 dp 배열을 초기화하는 역할을 합니다.dp 벡터를 크기 10001 × 4로 초기화합니다.dp.. 2025. 3. 4.
백준 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.

티스토리툴바