겜돌이의 개발일지

문제 백준 1756 1756번: 피자 굽기 첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋 www.acmicpc.net 풀이 오븐의 지름이 위에서부터 5 6 4 3 6 2 3 이라고 하면 i >=2일때, i번째 오븐의 지름은 i-1번째 오븐보다 큰 게 의미가 없어집니다. 따라서 오븐의 지름 5 6 4 3 6 2 3은 5 5 4 3 3 2 2 와 같습니다. 이렇게 정리해 준 후에는 도우가 들어갈 수 있는 인덱스를 찾아주면 됩니다. 이진 탐색으로 풀 수도 있고 끝에서 부터 루프를 돌며 풀 수도 있었습니다. 소스 코드 루프 1 2 3 4 5 6 7 8..

문제 백준 5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 점화식이 은근 간단한데 구현에 시간이 오래걸렸습니다. dp[i][j]는 i+1번째 차례에 +, - 연산으로 숫자 j를 만들 수 있는 경우의 수를 뜻합니다. dp[0][num[0]] 부터 시작하므로 1을 넣어줍니다. 그 후 루프를 돌면서 dp[i-1][j]값이 0보다 클 경우(가는 방법이 존재할 경우) 더한 값과 뺀 값을 비교하여 조건(0이상 20이하)을 만족한다면 dp에 저장합니다. 루프가 끝난 뒤 num[N-1] 값이 나오는 경..

문제 백준 2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 N자리 숫자에서 K개만큼을 꺼내 줘야 합니다. 예제 입력 3의 경우를 보겠습니다. 10 4 4177252841 10자리 숫자에서 4자리를 제거해 가장 큰 숫자를 만들어야 합니다. 스택이 비지 않았고, 꺼낼 수 있으며, 현재 넣을 수가 stack의 top보다 클 때 stack을 pop 하고, cnt를 증가시켜줍니다. [1번째 자리] 스택에 4를 push 합니다. (stack : 4) [2번째 자리] 1은 4보다 크지 않으므로 스택에 psuh 합니다. (stack : 41) [3번째 자리] 7은 1보다 크므로 스택을 ..

문제 백준 16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 bfs로 나라를 돌면서 인구 수 차가 일정 범위 이내라면 q, checkq에 push 합니다. bfs가 끝난 뒤 checkq에 있는 나라들의 인구를 같게 만들어줍니다. 인구 이동이 발생하지 않을 때 까지 이 과정을 반복하고, 횟수를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..

문제 백준 2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 내림차순으로 정리하는 우선순위 큐 pq를 선언합니다. pq에 숫자를 push 해주고, pq의 크기가 n보다 크다면 pq에서 pop 해줍니다. 이렇게 n*n번째 까지 반복한다면 n번째 큰 수가 제일 앞에 위치하게 됩니다. 이 수를 pq.top()으로 출력합니다. 소스 코드 12345678910111213141516171819202122232425#include#include#include#includeusing namespace std; int ..

문제 백준 2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 전형적인 bfs 문제였습니다. 먼저 치즈의 개수를 세주고 temp에 저장합니다. (0,0)은 무조건 공기이므로 bfs를 이용해 공기와 맞닿은 치즈들을 모두 공기로 바꿔줍니다. 다시 치즈의 개수를 세고, 치즈가 없다면 temp와 hour를 출력하고 있다면 bfs를 반복합니다. 소스 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253..