https://www.acmicpc.net/problem/1756 1756번: 피자 굽기 첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 d >> n; oven[0] = 1000000001; // 10억 + 1 // 위 칸 오븐보다 반지름 크면 // 아래 칸은 위 칸 통과 못한 피자는 못 들어옴 for (int i = 1; i > depth; if (depth > oven[i - 1]) oven[i] = oven[i - 1]; else oven[i] = depth; } for (int i = 1; i > r; pizza.push(r); } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NUL..
https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net dfs와 그리디를 합친 문제였습니다. 처음에는 dfs만으로 생각해서 풀려했는데 간단히 경로 찾기 개념만을 적용하면 겹치는 구간이 많고 복잡해졌습니다. 좀만 더 생각하니 해당 경로는 대각선 오른 위, 오른쪽, 대각선 오른 아래 방향으로만 움직일 수 있으므로 맨 위의 점부터 탐색을 하며 최대한 위쪽으로 가스관을 연결하면 됨을 깨달았습니다. 그리하여 dfs를 1,1 위치부터 r,1 위치 순으로 진행하며 dfs 내부에서..
https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net S, Y로 입력이 5*5 로 주어져 있을 때 가로, 세로로 인접한 7명을 뽑았을 때 S가 4명 이상을 이루는 경우의 수를 구하는 문제입니다. 처음에는 단순히 dfs로 돌려서 5*5 이기에 모든 지점에서 시작해서 dfs를 돌면서 S가 4개 이상인 경우를 고르고 중복인 경우는 제외하려고 했으나 반례가 존재했습니다. (문제의 테스트 케이스) 이와 같은 경우는 한붓그리기처럼 한 번에 쭉 이을 수 있는 경우만..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 처음에는 cnt 배열 (해당 위치에 도달하는 최소 횟수)를 2차원 배열로 잡고 풀었는데 반례가 존재했습니다. y, x로 말처럼 이동할 수 있는 횟수가 남은 경우 (k번 남았을 때) 로 이동했는데 해당 위치의 이전 cnt 값이 같고, 그 당시에 말처럼 이동했던 횟수가 k보다 작으면 이후 진행에 더 최소로 갈 수 있지만 업데이트 되지 않습니다. 그러므로 cnt를 3차원 배열로 보고 말..
www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 전형적인 KMP 알고리즘 문제였습니다. KMP 알고리즘을 이용해 해당 부분 문자열이 나오면 true, 아니면 false만 판별하면 됩니다. 코드는 다음과 같습니다. #include #include #include #include #include using namespace std; string S; string P; vectorpi; void init() { cin >> S; cin >> P; } // 전처리 pi 배열 구하기 void ..