본문 바로가기

백준84

[15686] 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 무엇을 구현해야 하는지 한참을 헤맸다. 문제에서 최대 M개만 남겨두고 폐업한다는 말을 이해하지 못해서 삽질하다가 구글링의 힘을 빌렸다. 총 치킨집의 개수는 M과 같거나 M보다 크다고 본문에 나와있다. 따라서 총 치킨집의 개수 중에서 M개만 뽑아야 하는 조합 문제이다. 이걸 몰라서 1시간을 삽질 굳~ 그럼 조합은 혼자서 구현했냐고 물으신다면~ 그러지 못했다. 처음에는 모든 경우.. 2023. 4. 10.
[14891] 톱니바퀴 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 구현/시뮬레이션 문제이다. 여기서 중요한 것은 톱니바퀴가 순차적으로 움직이는 것이 아닌 일괄적으로 움직인다는 것이다. 이것 때문에 참 힘들었지만 내 이해력이 부족했던 거겠죵 첫 번째로는 4개의 톱니바퀴를 구조체 배열로 만들어주었다. struct tobni { deque wheel; }; struct tobni tobni[5]; deque는 앞/뒤로 push와 pop이 가능한 container.. 2023. 4. 8.
[14503] 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 단순한 구현 문제인데 좀 조건이 복잡하다. 대신 작동 조건 순서대로 구현하면 문제 없다. 일단 작동을 멈추는 조건은 딱 한 가지이다. 뒤쪽 칸이 벽이라서 후진이 불가능할 때만 멈춘다. 이에 관련해서만 break를 걸어주고 while문으로 반복하면 된다. 일단 현재 칸이 청소되어있는지 따지는게 첫번째, 그 다음 주변 4칸(동, 서, 남, 북)이 청소.. 2023. 4. 7.
[13458] 시험 감독 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 단순한 사칙 연산 문제인데 정답률이 28%였다. 나도 틀렸다. (?) 자료형 범위가 포인트인 문제였다 ^.^, , 시험 감독 수의 최댓값은 한 시험장당 100만명이 필요하면서 총 100만개의 시험장이 있는 경우이다. 따라서 (10^6)*(10^6) = 10^12라는 것. int 쓰면 오답이 나온다. long int로 바꾸었더니 성공! #in.. 2023. 4. 6.
[14501] 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net Dynamic Programming 문제이다. 사실 잘 몰라서 구글의 힘을 빌렸다. 오랫동안 안하다보니 머리가 굳은 것 같다ㅠㅠ A[i]를 i일에 받는 최대의 금액이라고 정의한다. 또한 받는 돈은 업무가 끝난 후 다음날에 들어온다고 가정한다. 1) i번째 날에 일한 경우 퇴사날을 넘기면 안되므로 조건문을 만든다. i+T[i]> N; for (int i = 1; i > T[i] >> P[i]; } // 그 다음날에 돈이 들어온다고 가정 for (int i = 1; i 2023. 4. 5.
[11444] 피보나치 수 6 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 분할 정복 문제이다. 사실 행렬을 잘 몰라서 구글링을 진행함 ㅎㅎ 공식은 구글링을 참고했고 코드는 혼자 짰다! 참고한 공식 유도 그래서 도출된 식이 맨 아래에 있는 식이다. 행렬의 거듭제곱을 알아야 풀 수 있기 때문에 행렬 곱셈 + 분할정복을 이용한 거듭제곱을 이용하여 풀었다. 이번엔 수의 범위가 굉장히 컸기 때문에 모든 자료형을 long long으로 설정해주었다. #include using namespace std; long long n; // 행렬 계산 long long.. 2023. 2. 8.
[10830] 행렬 곱셈 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 분할 정복 문제이다. 이건 앞에서 했던 두 개의 문제를 동시에 쓰는 것이다. https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 .. 2023. 2. 8.
[1629] 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할 정복 문제이다. 거듭제곱을 분할정복으로 풀 수 있다는 것을 처음 알게 되었다! 제곱하는 횟수가 짝수라면 위의 식을, 홀수라면 아래식을 이용하면 된다. 세상에는 참 천재가 많은 듯 ,, 이렇게 한다고 끝이 아니고 숫자가 너무 커질 것을 대비하여 C로 나눈 나머지를 출력해야한다. 따라서 모든 계산 과정에다가 "%C"를 붙여주었다. 그리고 범위를 생각하여 long long으로 잡았다. 안그러면 오류 난다! #include using namespace std; l.. 2023. 2. 6.
[1992] 쿼드트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 분할 정복 문제이다. 왜 정수 입력이 안되지 의문이었는데, 띄어쓰기가 안 돼있는 걸 인식하지 못했었다. ㅋ 그래서 string으로 한 줄 받고 parsing 해주며 입력 부분을 처리했다. 그 다음 중요한 건 괄호 처리! 입력 순서는 아래와 같은 것을 확인했다. 이걸 참고해서 예제 1을 검사해보면 이렇게 된다. 영역이 시작할 때 괄호가 열려야 하고, 영역이 끝나면 괄호가 닫혀야 한다. .. 2023. 2. 4.
[1780] 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 분할 정복 문제이다. 재귀 함수를 통해 계속해서 한 변의 길이를 줄여가면서 종이 내부의 숫자가 모두 동일한지 검사한다. 재귀 함수를 진행할 때 필요한 파라미터는 한 변의 길이와 빨간색 칠한 행/열의 시작점이다. 또한 9개의 종이로 분할해야하므로 재귀 함수 안에 9개의 재귀 함수를 호출하였다. 한 변의 길이가 1이면 더 이상 쪼갤 수 없으므로 재귀 함수를 종료하였다. #include us.. 2023. 2. 3.

티스토리툴바