출발 조건이 까다로운 2차원 배열 목적지까지 이동하는 다이나믹 프로그래밍

14722번: 우유 도시 (0,0)에서 (n-1,n-1)까지 이동하면서 우유를 마시는데 맨 처음에는 딸기우유를 마신다 딸기우유를 마신 다음에 초코우유를 마신다 초코우유를 마신 다음에 바나나 우유를 마신다 바나나 우유를 마신 다음에 딸기 우유를 마신다 위 4가지 조건을 만족하면서 우유를 마시는데, (x,y)에는 딸기, 초코, 바나나 우유 셋 중 하나만 있다.  최대로 마실 수 있는 우유 개수는? ------------------------------------------------------------------------------------------------------------------------------------------------------ dp[i][j][k] = (j,i)에 있는데 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 1. 27.
• textsms

ABC 348 D번 복기 - 그래프를 재구성하고 BFS/DFS를 해야하는 문제

https://atcoder.jp/contests/abc348/tasks/abc348_d D - Medicines on Grid AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 자체는 어디서나 많이 보던 기본적인 BFS/DFS 셋팅이다 2차원 맵에 특정 위치에 약이 있는데, 이 약을 먹으면 에너지가 E로 된다. 이동할때마다 에너지가 1씩 감소한다 약은 먹어도 되고 먹지 않아도 되는데, 단 1번만 먹을 수 있고 먹으면 사라진다 에너지 0부터 시작한다고 할때, 목표로 하는 지점에 도착할 수 있는가? 그냥 기본적인 BFS..

• format_list_bulleted Atcoder
• · 2024. 4. 10.
• textsms

DP가 불가능할 때 특정 위치 (x,y)로 이동하는 경우의 수를 구하는 다른 방법

SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나이트가 (i,j)에 있을때, (i+1,j+2), (i+2,j+1) 둘 중 하나로만 움직일 수 있다고 하자. x,y가 주어질 때, (0,0)에서 출발하여 (x,y)로 이동할 수 있는 경우의 수는? dp[y][x] += dp[y-1][x-2], dp[y][x] += dp[y-2][x-1]로 구할 수 있을 것 같은데 X,Y가 $10^{6}$까지라서 메모리도 안되고 $O(N^{2})$이라 시간복잡도도 안된다 나이트가 (i,j)에서 이동하는 방법이 (i+1,j+2), (i+2,j+1) 2가지만 있다는 것을 생각한다면... (0,0)에서 (..

• format_list_bulleted 조합론
• · 2024. 4. 5.
• textsms

ABC 337 D번 복기 - 2차원 배열에서 행,열로 연속한 O의 개수를 빠르게 세는 방법(sliding window + prefix sum)

D - Cheating Gomoku Narabe (atcoder.jp) D - Cheating Gomoku Narabe AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp . o x로 이루어진 2차원 배열에서 .을 o로 바꿀 수 있다. 이 때 행이나 열로 연속한 o의 개수가 k개가 되도록 최소로 바꾸는 횟수 처음에 DFS로 o의 좌표에서 시작해서 .을 o로 바꿔서 해보다가 당연히 시간초과났고 그러다가 행이나 열 각각에서 모두 조사해보면 된다는 생각이 들었다 여기까지는 좋았음 행 한줄에서 어떻게 .을 o로 바꿔야 연속한 o의 ..

• format_list_bulleted Atcoder
• · 2024. 1. 21.
• textsms

ABC 332 D번 복기 - 행,열 바꿔서 다른 2차원 배열과 똑같이 만드는법(BFS가 된다고?)

1. 문제 D - Swapping Puzzle (atcoder.jp) D - Swapping Puzzle AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 비슷한 문제들이 그리디로 풀려가지고... 숫자 다르면 무조건 바꾸는 그리디인가도 생각해봤는데.. 제한이 H,W가 5 이하라서 완전탐색이 가능할 것 같다고 생각을하고, 생각까진 하더라도 완전탐색을 어떻게 해야할지.. 근데 그 전에 문제부터 제대로 못읽었던것도 문제.. Choose an integer i satisfying 1≤i≤H−1 and swap the i..

• format_list_bulleted Atcoder
• · 2023. 12. 11.
• textsms

정육면체가 쌓인 3차원 도형의 겉넓이를 구하는 방법

1. 문제 16931번: 겉넓이 구하기 (acmicpc.net) 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어 www.acmicpc.net 2. 풀이 위,아래, 앞,뒤,왼쪽,오른쪽에서 보이는 면의 개수를 전부 더하면 될 것이며 면의 개수는 어떻게 구하지? n*m 크기의 바닥 아래에 정육면체를 쌓았을때, 위나 아래에서 봤을때는? 당연히 n*m개씩 보일 것이다. 왼쪽과 오른쪽에서 봤을때는? 위 그림이 1 3 4 2 2 3 1 2 4 와 같이 주어지는데, 왼쪽에서 본다면, 1 3 4 >>>>>> 2 2 3 1 2 4 처럼 상상해본..

• format_list_bulleted 기하학
• · 2023. 8. 25.
• textsms