본문 바로가기

PS15

[BOJ 18870] 좌표 압축 문제 링크 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 아이디어 '좌표압축' 기법은 PS에서 종종 쓰이는 기법으로, 큰 범위의 값을 갖는 좌표들을 정렬하여 다시 순서를 부여함으로써, 더 작은 범위 내로 압축 시키는 것이다. 가령 1차원 x축 위의 [1, 1e9] 의 값을 갖는 어떤 1만 개의 좌표를 생각해보자. count[t] = x축의 값이 t인 좌표의 개수라고 할 때, t = [1, 1e.. 2020. 7. 16.
[BOJ] 어른 상어 문제 링크 https://www.acmicpc.net/contest/problem/517/3 C번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 아이디어 시뮬레이션 문제에 주어진 로직을 정리하면 다음과 같다. 1. 생존한 상어들은 현재 위치에 냄새를 뿌린다. 2-1. 생존한 상어들은 우선순위에 따라 상하좌우 중 냄새 없는 칸으로 이동한다. 2-2. 인접한 칸에 냄새없는 칸이 없다면, 우선순위에 따라 상하좌우 중 자신의 냄새가 있는 칸으로 이동한다. 3. 이동한 칸에 여러 상어가.. 2020. 6. 9.
[BOJ 19236] 청소년 상어 문제 링크 https://www.acmicpc.net/contest/problem/19236 B번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 데이터 검증을 위해 "대회 - 연습" 에 새로 올라온 문제인데, 아마도 유형이나 시기를 보면 이번 2020년 상반기 삼성 코테 기출인듯 하다. 아이디어 시뮬레이션으로 주어진 순서에 따라 구현하자. 1. 상어는 (0,0)에 들어가 그 칸의 물고기를 잡아 먹고 그 물고기의 방향을 얻는다. 2. 1번 물고기부터 16번 물고기까지 살아 있다면, 문제에 주어진대로 이동한.. 2020. 6. 9.
[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.

티스토리툴바