본문 바로가기

백준85

[BOJ] 20056 : 마법사 상어와 파이어볼 문제 링크 20056번: 마법사 상어와 파이어볼 (acmicpc.net) 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 마법사가 된 상어가 파이어볼에 내린 명령을 구현하는 문제. 이전에 풀었던 아기상어 문제의 연관 문제인 것같다. 풀이 파이어볼은 크기가 N x N인 격자에서 움직이며 1번 행과 열은 각각 N번 행과 열과 연결되어있다. 즉 파이어볼이 격자 밖으로 나가는 일은 없다. 모든 파이어볼은 명령 1번당 1회씩 이동한다. 그리고 이동 후 한 칸에 여러개의 파이어볼이 .. 2022. 5. 24.

[BOJ] 20055 : 컨베이어 벨트 위의 로봇 문제 링크 20055번: 컨베이어 벨트 위의 로봇 (acmicpc.net) 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 컨베이어의 회전을 구현해서 내구도가 0인 칸이 K개 이상 생겼을 때 수행중이던 단계가 몇 단계인지 출력하는 문제. 풀이 컨베이어는 위의 그림처럼 1부터 2N번째까지 칸으로 이루어져있고, 1번 칸을 "올리는 위치" 즉, 새로운 로봇을 올리는 위치이고, N번 칸을 "내리는 위치" , 로봇이 내려오는 위치이다. 컨베이어 벨트의 각 칸을 표현하는 방식은 여러가지가 될 것이다... 2022. 5. 23.

[BOJ] 19238 : 스타트 택시 문제 링크 19238번: 스타트 택시 (acmicpc.net) 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 모든 손님을 최단거리로 태우고 싶어하는 백준이를 도와주자. 풀이 백준이가 운전하는 택시는 현재 위치에서 가장 가까운 손님을 태우고, 그 손님을 목적지로 데려다준다. 만약 연료가 부족해서 손님을 태우지 못하거나, 손님을 태우고 목적지까지 가지 못한다면 -1을 출력하고 종료한다. 연료가 충분해서 손님을 태워서 목적지에 데려다 줄 수 있다면, 손님의 위치에서 목적지까지.. 2022. 5. 23.

[BOJ] 17825 : 주사위 윷놀이 문제 링크 17825번: 주사위 윷놀이 (acmicpc.net) 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 주사위로 진행되는 윷놀이를 규칙대로 구현하는 문제. 풀이 왼쪽과 같은 윷놀이 판을 어떻게 구현할지가 일단 첫번째 문제였다. 파란색 칸을 밟았을 때 경로가 바뀌는 것을 어떻게 표현해야하지 생각하다가, 처음엔 10, 20, 30 칸을 밟을때마다 경로가 바뀌니까 4가지 경우의 경로를 따로 만들려고 했었다. 하지만 그렇게하면 이동할 칸에 이미 말이있는지 파악하기가 힘들었다. 그래서 나는 내 임의대로 각 칸마.. 2022. 5. 19.

[BOJ] 17822 : 원판 돌리기 문제 링크 17822번: 원판 돌리기 (acmicpc.net) 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 정해진 규칙에 따라 원판을 돌리는 시뮬레이션 문제. 풀이 i번 원판을 배열로 표현했을 때 원판이 회전하게 되면 사실 한 칸 씩 당기거나 밀어서 원판의 회전을 표현할 수 있다. 빨간색 숫자를 배열의 인덱스라고 생각했을 때 시계방향으로 회전하게되면 배열의 값들을 한 칸씩 오른쪽으로 밀어서 회전을 표현할 수 있다. 그리고 마지막 3번 인덱스에 있던 값이 첫 인덱스 0으로 오게된다. 배열의 값.. 2022. 5. 18.

[BOJ] 17779 : 게리맨더링 2 문제 링크 17779번: 게리맨더링 2 (acmicpc.net) 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 구역별로 선거구를 나눠서 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구하는 문제. 선거구를 나누는 구현문제이다. 풀이 어떻게 선거구를 나눠야 인구 분포가 고르게 될지는 방법이 따로 없다. 모든 경우를 다 따져봐야한다. 5번 선거구의 경계를 좌표로 나타내보면 위와 같다. 따라서 d1, d2는 다음의 조건을 만족해야한다. y - d1 >= 1 && y + d2 2022. 5. 18.

[BOJ] 17142 : 연구소 3 문제 링크 17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 모든 칸에 바이러스를 퍼트리는데 걸리는 시간을 구하는 BFS 문제. 풀이 연구실을 N X N 크기의 칸으로 표현했을 때 각 칸은 0 빈 칸, 1 벽, 2 바이러스 중에 하나로 채워진다. 바이러스에는 활성 바이러스와 비활성 바이러스가 있다. 둘다 바이러스지만 활성 바이러스는 전염성을 가지고 비활성 바이러스는 전염성이 없다. 하지만 활성 바이러스가 비활성 바이러스와 만나면 활성화시킬 수 있다. 2 ~ 10개 .. 2022. 5. 17.

[BOJ] 5373 : 큐빙 문제 링크 https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 큐브 돌리는 것을 구현하는 구현문제. 풀이 정말 그냥 노가다로 큐브를 돌릴때마다 6면의 변화를 구현하는 구현문제이다. 큐브를 한 번 돌리면 돌릴 때 바라보고있는 면의 반대쪽 면을 제외한 5면은 회전 후 구성이 바뀐다. 바라보고 있는 면은 돌리는 방향에 따라 시계방향 또는 반시계 방향으로 큐브가 바뀔 것이고, 바라보고 있는 면과 접하는 4개의 면은 9칸 중 3칸이 회전한다. 큐브를 돌리면 .. 2022. 5. 16.

[BOJ] 11758 : CCW 문제 링크 11758번: CCW (acmicpc.net) 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net CCW 문제 풀이 처음에 나는 CCW라는 알고리즘이 있는 줄 모르고 직접 기울기와 방향을 구해서 문제를 해결하려했다. 이건 아닌것같아서 구글링 하다가, 그럼 그렇지 CCW 알고리즘이 있는 걸 알았다. CCW란 Counter Clockwise의 줄임말로 점 A,B,C가 주어졌을 때 시계방향으로 놓여있는지, 일직선상에 놓여있는지, 반시계방향으로.. 2022. 5. 12.

이전 1 2 3 4 5 ··· 10 다음

티스토리툴바