본문 바로가기
반응형

Problem Solving155

백준 14501 : 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [ 문제풀이 ] 정해는 다이나믹 프로그래밍이지만 N이 워낙 작기 때문에 완전 탐색을 기반으로 해결해도 되는 문제이다. 나는 다이나믹 프로그래밍을 이용해서 해결하였다. ​먼저 다음과 같은 dp 테이블을 정의하자. dp[i] : i번째 날 얻을 수 있는 최대 수익 위와 같은 정의를 통해 우리는 dp[i]는 최대 수익이 들어있다고 가정할 수 있다. 그렇다면 점화식은 어떻게 도출할 수 있을까? ​j번째 날과 j번째 상담을 하고 걸리는 기간(T[j])이 현재 i번째 날보다 작거나 같으면 j번째 날의 최대 비용에 i번째 날의 상담을 하는 비용을.. 2021. 8. 1.
백준 14500 : 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net [ 문제풀이 ] 테트로미노로 만들 수 있는 모든 종류(회전, 대칭)를 만들어 종이에 놓을 수 있는 모든 경우의 수를 구하면 해결할 수 있는 문제이다. ​종이를 회전시키는 방법도 있고 여러 가지 방법이 있겠지만 나는 간단하게 테트로미노로 만들 수 있는 모든 종류를 미리 만들어서 해결하였다. ​대칭, 회전을 통한 만들 수 있는 모든 종류는 다음과 같다. 이를 3차원 배열로 표현하면 다음과 같다. st.. 2021. 8. 1.
백준 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번 면이 항상 아래 면으로 오도록 구현하였다. 동쪽으로 주사위를 굴리는 경우 : (3, 6), (1, 3), (4, 1)을 swap 해주면 된다. 서쪽으로 주사위를 굴리는 경우 : (6.. 2021. 8. 1.
백준 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 [ 문제풀이 ] 브론즈 2의 난이도답게 정말 쉬운 문제이다. 각 시험장마다 총감독관을 1명 배치하고 남은 응시자 수를 마크할 수 있도록 부감독관을 배치하면 해결할 수 있다. ​조심해야 할 점은 정답의 범위이다. 시험장의 개수 100만, 각 시험장에 있는 응시자 수 100만, 총감독관과 부감독관이 응시할 수 있는 수가 1인 최악의 경우 100.. 2021. 8. 1.
백준 3190 : 뱀 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net [ 문제풀이 ] 전형적인 시뮬레이션 문제이다. 문제의 조건을 잘 읽어보면 결국 가장 중요한 것은 뱀의 머리와 꼬리를 어떻게 관리할 것인가?이다. N이 최대 100이기 때문에 뱀의 길이는 최대 100 x 100의 길이밖에 될 수 없다. 결국 시간 또한 100 x 100을 넘길 수가 없다. 이후부터는 자신의 몸에 부딪힐 수밖에 없기 때문이다. ​따라서 시간별로 뱀의 몸통 위치와 머리 부분, 꼬리 부분의 좌표.. 2021. 8. 1.
백준 12100 : 2048(Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net [ 문제풀이 ] 이번에도 마찬가지로 전형적인 시뮬레이션 문제이다. 2048 게임은 워낙 유명하기 때문에 문제를 이해하는 데는 어려움이 없을 것이다. ​4방향으로 이동해야하는 문제는 4방향 함수를 모두 구현하는 것보다 맵을 회전하여 4개를 만든 후 한 가지 방향으로 이동시키는 메서드를 구현하는 것이 구현하기에 훨씬 편할 것이다. 삼성 문제는 시간 복잡도가 넉넉하기 때문에.. 2021. 8. 1.
백준 13460 : 구슬 탈출 2 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [ 문제풀이 ] 삼성 기출문제는 대부분 시뮬레이션 or 완전 탐색 문제이다. 이 문제는 매번 새로운 맵을 만들어주면서 모든 경우의 수를 확인하면 해결할 수 있다. ​주의해야 할 점은 빨간 구슬과 파란 구슬 중 어떤 구슬을 먼저 움직이느냐를 판단하는 것이다. 현재 map이 다음과 같은 형태라고 하자. # # # # # # O # # B # # R #.. 2021. 8. 1.
백준 1027 : 고층 건물 https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net [ 문제풀이 ] N이 최대 50이기 때문에 모든 빌딩을 빌딩 위치부터 좌측(우측)을 탐색하면서 가장 최근에 구한 고층빌딩의 기울기보다 작은(큰) 빌딩들의 개수를 구해주면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; .. 2021. 8. 1.
백준 1461 : 도서관 https://www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net [ 문제풀이 ] 최소 걸음을 구하는 것이기 때문에 가장 먼 곳에 있는 책은 마지막에 옮겨야 한다. 마지막에는 0으로 돌아올 필요가 없기 때문이다. 또한, 책 한개를 옮길 때 M개의 책을 함께 옮길 수 있으니 남은 책들중에서 거리가 먼 책을 먼저 옮겨야 한다. 따라서 두 조건 모두 거리가 먼 책이 우선순위가 높기 때문에 정렬을 먼저 해준다. 정렬전: -37 2 -6 -39 -29 1.. 2021. 7. 31.
반응형

티스토리툴바