devlog

출처 : 10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 방법 계단 수는 +1 또는 -1 차이가 난다. dp[i][j]를 i자리 수 이면서 j로 시작하는 수로 잡는다 그러면 dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1] 이 된다 주의할 점은 j가 0이면 1로 시작하는 수만 와야하고 j가 9면 8로 시작 한느 수만 올 수 있어 예외 처리를 해주면 된다. //11057 #include using namespace std ; int n; vector num; long long dp[101][10]; long long ans = 0; void solv..

출처 : 2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 방법 현재 인덱스 포도주를 기준으로 몇 번 연속인지 계산하면 문제를 쉽게 풀이할 수 있다. 0번째 연속인 경우 dp[i] = dp[i-1] // i번째 포도주를 마시지 않는 경우 1번째 연속인 경우 dp[i] = dp[i-2] + wine[i] // i-2 번째 dp에서 i-1번째 포도주를 건너뛰고 i번째 포도주를 마신 경우 2번째 연속인 경우 dp[i] = dp[i-3] + wine[i-1] + w..

출처 : 2638번: 치즈 (acmicpc.net) 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 방법 dfs로 풀이하였다 모눈종이의 가장자리가 비어있다고 가정했으므로 치즈 밖의 공기들은 다 연결되어있다. 치즈 밖의 공기는 다 연결되어있으므로 dfs(0,0)으로 하면 다 탐색할 수 있다. 탐색 중 보드 값이 1인 치즈를 만나면 +1을 해주어 보드 값을 2로 만들어 주고 탐색중 보드 값이 2인 치즈를 만나면 mel_cheese벡터에 추가해 주고 visited 값을 1로 바꾸어 주어 다시 방문..