본문 바로가기

전체 글36

[BOJ 14503] 로봇청소기 문제 링크 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 아이디어 * 아래와 같이 문제에 주어진대로 시뮬레이션한다. 1. 현재 위치가 청소되지 않았다면 청소한다. 2. for (4번) { 2-1. 왼쪽으로 90도 회전한다. 2-2. 바라보는 방향의 앞 칸이 청소되지 않았다면 전진하여 1로 돌아간다. 2-3. 바라보는 방향의 앞 칸이 청소되어 있다면 2-1로 돌아간다. } 3. 모든 방향의 청소가 되어 있을 때(2-2를 한 번도 실행하지 않았.. 2020. 5. 15.
[BOJ 14499] 주사위 굴리기 문제 링크 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 아이디어 주사위를 굴리는 것의 구현은 주사위의 6개 면에 전개도에 나와있는 숫자로 각각 idx를 부여하면 간단하다. 마주보는 idx끼리 짝을 이루어보면 (1,6), (2,5), (3,4)로 (x, 7-x)꼴을 이루는 것을 확인 할 수 있다. 주사위를 보았을 때, u, f, s를 각각 윗면, 정면, 오른쪽면의 idx라고 하.. 2020. 5. 14.
[BOJ 1421] 나무꾼 이다솜 문제 링크 https://www.acmicpc.net/problem/1421 1421번: 나무꾼 이다솜 첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나씩 주어진다. N은 1,000보다 작거나 같은 자연수이고, C와 W는 10,000보다 작거나 같은 자연수이다. 그리고 나무의 길이는 모두 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 아이디어 나무가 1,000개 이하 ,나무의 길이가 10,000 이하이기 때문에 나무를 자르는 단위를 1부터 10,000까지 완전탐색 해도 시간 안에 해결할 수 있다. 가지고 있는 나무 중에서 가장 긴 나무.. 2020. 5. 8.
[BOJ 1411] 비슷한 단어 문제 링크 https://www.acmicpc.net/problem/1411 1411번: 비슷한 단어 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 각각의 단어는 모두 다르다. www.acmicpc.net 아이디어 문자열 단순 구현 1. 같은 문자가 다른 문자로 바뀌는 경우 (aa -> bc) 2. 다른 문자가 같은 문자로 바뀌는 경우 (bc -> aa) 위의 두 가지 경우를 제외하고는 모두 바꿀 수 있다. 소스코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false);.. 2020. 5. 7.
[BOJ 1564] 팩토리얼5 문제 링크 https://www.acmicpc.net/problem/1564 1564번: 팩토리얼5 첫째 줄에 정수 N이 주어진다. N은 1,000,000보다 작거나 같다. 또, 9보다 크거나 같다. www.acmicpc.net 필요한 지식 모듈러 연산의 성질 $$(A*B) modC=((A mod C)*(B mod C)) mod C$$ 곱셈에 대한 증명은 아래와 같으며 모든 사칙연산에 대해 성립한다. 주의할 점 문제에서 0이 아닌 뒤 다섯자리를 요구하기 때문에 MOD를 1e5로 잡을지도 모른다. 하지만 xxxx50272 * 9500을 세로식으로 계산하면, xxxx7854000까지만 알 수 있다. 즉 뒤의 이어지는 0을 모두 지울 경우 7, 8, 5, 4 네 개의 수만을 알 수 있는 것이다. 그렇기 때문에.. 2020. 5. 4.
[BOJ 1166] 선물 문제 링크 https://www.acmicpc.net/problem/1166 1166번: 선물 첫째 줄에 N L W H가 주어진다. 모든 값은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 아이디어 이분 탐색을 통해, L*W*H의 박스안에 A*A*A의 박스가 N개 이상 들어가도록하는 A의 최대값을 찾는다. 주의할 점 L, W, H는 최대 1e9이기 때문에 num의 최대값은 1e27라고 생각할 수 있다. 이 때, 1e27은 8byte의 long long int로도 표현할 수 없는 큰 수이다. 하지만 N=1e9일 때, mid의 최소값은 1e3이며 따라서 num의 최대값은 1e18로 long long int로 커버 가능하다. 이분 탐색의 반복문을 while (hi - lo .. 2020. 4. 30.

티스토리툴바