본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/구현, 시뮬

 (65)
[백준 / BOJ] 9944 N*M 보드 완주하기 문제 출처 : https://www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net N*M크기의 보드에 장애물(*) 빈칸(.)이 있다 보드의 빈칸위에 놓인 공은 다음 규칙에따라 움직인다. 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다. 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다. 게임은 공이 더 이상 이동할 수 없을때 끝난다. 모든 빈칸을 방문하기위한 이동횟수의 최솟..
[백준 / BOJ] 18500 미네랄 2 (Java) / 2933 미네랄 1 포함 미네랄 2 기준으로 설명을 하겠다. (미네랄 1(2933번)과 2는 동일한 문제인데, 미네랄1이 테스트케이스가 좀더 빡샌거로 알고있다.) 실제로 동일 코드를 제출하면 모두 맞았습니다가 나온다. 문제 출처 : https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 창영이와 상근이가 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 던져 싸우고있는데, 막대기가 날아가다 미네랄을 만나면, 해당 미네랄은 파괴되고 막대기도 이동을 멈춘다. 이때, 해당 미네랄이..
[백준 / BOJ] 17780 새로운 게임 (Java) 문제 출처 : https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net (...) 풀이 문제에서 주어진 그대로 풀면되는 시뮬레이션 문제였다. 문제 해석시 주의할점이 있었는데, 1. 다음 위치가 빨간색인데, 이동할 위치에 이미 다른 체스말들이 있는경우, 이동후 체스말을 위로 쌓은다음에 체스말의 순서를 뒤집는것이 아니라, 이동 전에 뒤집고 체스말을 위로 쌓는것이다. 예를들어, 현재 이동할 체스말들이 (1,2,3) 순서대로 쌓여있고 이동위치에 이미 (4,5)..
[백준 / BOJ] 1938 통나무 옮기기 문제 출처 : https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4
[백준 / BOJ] 17135 캐슬 디펜스 문제 출처 : https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net N*M배열에 적이있고 N-1번째 줄에 궁수가있다. 매 턴마다 궁수는 자기의 사정거리안에서 가장 가까운적(가까운적이 여러명이라면, 가장 왼쪽적)을 찾아 공격하고 궁수의 공격이 끝난후 적은 한칸 아래로 내려온다. 궁수는 일제히사격하므로, 한 적에게 여러궁수가 공격할수있다. 이때, 가장많은 적을 없애는 경우의 수를 구하는 문제다. 풀이 시뮬레이션 문제였다. 최악의경우 (N=15, M=15)일때 반복..
[백준 / BOJ] 14500 테트로미노 문제 출처 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net N*M크기의 종이에 숫자들이 쓰여있다. 이 종이에 테트로미노하나를 놓았을때, 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 찾는 문제다. 소스코드 완전탐색으로 푼 문제다. 종이의 세로,가로가 각각 최대 500이며, 한번 탐색마다 (모든 폴리오미노를 본다했을때,) 40번이라고 하면, 총 탐색횟수는 250000*40 = 10000000가 되어서 시간초과를 피할수있..
[백준 / BOJ] 16985 Maaaaaaaaaze 문제 출처 : https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 미로를 나타내는 5*5크기의 판이 5개 주어진다. 판의 각 칸에는 이동할수없는칸 0, 이동할수있는칸 1이 있다. 5개의 판은 자유롭게 쌓을수있고 각 판마다 자유롭게 90도 회전또한 가능하다. 이때, 판을 적절히 쌓고 적절히 회전해서 5*5*5크기의 미로를 탈출하는 최소 이동횟수를 구하는 문제다. 입구는 5*5*5크기의 그리드의 각 모서리이며 출구는 입구와 면을 ..
[백준 / BOJ] 8980 택배 문제 출처 : https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net C만큼의 용량을 실을 수 있는 트럭이 있다. N개의 마을이 있으며, A마을에서 B마을로 용량 D의 택배를 보낼려고한다. M개의 보낼 택배의 시작장소, 도착장소 용량이 주어질때 트럭 한 대로 보낼 수 있는 최대한 많은 택배의 양을 구하는 문제다. 풀이 모든 경우를 봐줄경우, 구현에 따라 최악의 경우 2^M번 반복하므로 완전탐색으로는 시간안에 풀기 힘들다. 그리디를 ..

티스토리툴바