본문 바로가기

전체 글321

백준 4811 c++ "알약" -PlusUltraCode- https://www.acmicpc.net/problem/4811 [필자 사고]DP 탑다운 및 바텀업 둘다 가능한 문제다.필자는 바텀업 방식으로 풀었고 해당 문제만의 특이한 매력은W가 반드시 먼저 와야 된다는 제약조건이다.즉 바텀업 방식으로 구현할때 H가 W보다 크면 절대로 안된다.반드시 H는 W보다 작아야 된다.사소한거지만 이러한 조건하나가 문제를 풀수 있을지 못할지를 결정하는걸 배웠따. 아래는 상세한 코드 해설이다.[코드 해설]2. DP 테이블 정의이 문제에서 DP 테이블 dp[w][h]는 다음을 의미합니다:w: 아직 쪼개지 않은 (Whole) 알약 개수h: 이미 반으로 쪼개져 있는 (Half) 알약 개수dp[w][h]: W(Whole)를 w개, H(Half)를 h개 사용했을 때 만들 수 있는 문자열.. 2025. 3. 6.
백준 2240 c++ "자두나무" -PlusUltraCode- https://www.acmicpc.net/problem/2240 [필자 사고]이 문제는 동적프로그래밍 문제이다.이 문제를 풀면서 확실히 동적프로그래밍에서 배열의 인덱스를 대하는 자세는 기존 배열 형태보다는flag느낌으로 사용해야 된다는걸 다시 한번 느꼈다.처음 배열에서는 time 두번째 배열은 pos 세번째 배열은 위치 이동 가능한 숫자 형태로 flag 형식으로 배열들을 선언하고해당 조건들이 성공될 때 데이터를 업데이트 해주는 식으로 문제를 해결했다.2차원에서 3차원으로 바꼇을 뿐인데 기존 고려할게 더 많아졌다. 아래는 자세한 소스코드 해설이다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 게임의 기본 정보를 입력받아 초기화하는 역할을 한다.T, W를 입력받아 각각 총 시간과 이동.. 2025. 3. 6.
백준 18405 c++ "경쟁적 전염" -PlusUltraCode- https://www.acmicpc.net/problem/18405[필자 사고]필자는 해당 문제를 BFS로 풀었다. 이 문제만의 특이 포인트는 다음과 같다.1. 작은 숫자들의 바이러스들 부터 퍼진다.2. 모든 숫자들의 바이러스가 퍼지게 되면 1초가 끝난다.3. 한번 퍼질때 주위 한칸밖에 퍼지지 못한다. 필자는 이러한 제약 조건들을 해결하기 위해 우선순위 큐와 일반 큐를 이용하여 문제를 해결했다.우선순위 큐에는 바이러스 번호들을 기준으로 작은 순서대로 정렬을 하였고 특정 위치들을 우선순위 큐에 넣어서 관리했다.(새로 생성된 바이러스 포함) 그리고 매번 큐로 BFS를 실행하여 바이러스 전파를 진행하였다.개인적으로 BFS와 우선순위 큐를 공부하기 좋은 문제였다. 아래는 자세한 코드 해설이다.[코드 해설]1. .. 2025. 3. 5.
백준 16928 c++ "뱀과 사다리 게임" -PlusUltraCode- https://www.acmicpc.net/problem/16928 [필자 사고]BFS문제이다.필자는 이 문제에서 배운점은 아래와 같다.한번 뱀 혹은 사다리를 만나게 되면 한번만 이동할 수 있는게 아니라 계속 이동할 수 있다는 것이다.그래서 while문을 이용하여 계속 이동할 수 있게 코드를 구성해야 된다.또한 vistied방문 처리를 2번 설정해야 완전하게 검사가 된다. 이 부분을 배우게 되었다. 좋은 문제였다.아래는 자세한 코드 해설이다.[코드 해설]1. 입력 처리 (Input 함수)먼저, 보드의 크기와 뱀 및 사다리 정보를 입력받습니다.N개의 사다리와 M개의 뱀을 입력받습니다.각각의 사다리와 뱀은 특정 칸에서 다른 칸으로 이동하는 역할을 합니다.이를 map[x] = y 형태로 저장하여, x번 칸에 .. 2025. 3. 4.

티스토리툴바