본문 바로가기

백준

 (233)
[백준 / BOJ] 1865 웜홀 (SPFA) 문제 출처 : www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀 www.acmicpc.net 백준이가 어느 지점에서 출발하여, 다시 시작지점으로 돌아왔을때, 출발하였을 시간보다 시간이 더 줄어들었는지 찾는문제이다. 만약 가능하다면, YES 아니라면, NO를 출력하면된다. (도로는 양방향이며, 시간을 되돌려주는 웜홀은 단방향이다) 풀이 음수가중치(워홀)가 존재하므로 벨만포드 혹은 SPFA로 풀어야한다. 문제 이해를 잘못하여 몇번 틀렸었다. 난 출발지점이 1이라고 생각하고 탐색을 했는데, ..
[백준 / BOJ] 11657 타임머신 (SPFA) 문제 출처 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net N개의 도시가 있다. 1번도시에서 출발하여 모든 도시로 갈때, 최소한의 시간으로 가는 경우를 구한다. 도시간의 시간에는 음수가 존재할수있으며, 이는 타임머신을 타고 과거로 가는경우이다. 만약 과거로 계속해서 갈수있으면 -1 을 출력하고 종료한다. 1번도시에서 해당하는 i번 도시로 갈수없다면 -1을 출력한다. 풀이 벨만포드 풀이 : dlw..
[백준 / BOJ] 11657 타임머신 (벨만포드) 문제 출처 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net N개의 도시가 있다. 1번도시에서 출발하여 모든 도시로 갈때, 최소한의 시간으로 가는 경우를 구한다. 도시간의 시간에는 음수가 존재할수있으며, 이는 타임머신을 타고 과거로 가는경우이다. 만약 과거로 계속해서 갈수있으면 -1 을 출력하고 종료한다. 1번도시에서 해당하는 i번 도시로 갈수없다면 -1을 출력한다. 풀이 음수가중치가 존재함으로,..
[백준 / BOJ] 1079번 마피아 문제 출처 : www.acmicpc.net/problem/1079 1079번: 마피아 첫째 줄에 참가자의 수 N이 주어진다. 둘째 줄에는 각 참가자의 유죄 지수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 참가자 번호가 주어진다. N은 16보다 www.acmicpc.net 은진이는 게임에서 마지막남은 마피아이다. 각 시민에게는 유죄지수가 있다. 1. 남아있는 시민의 수가 짝수일때는 밤이되서 시민을 한명 죽일수있다. 참가자 i가 죽었을때, 다른 참가자 j의 유죄지수는 R[i][j]만큼 변한다. 2. 낮에는 살아있는 참가자중 유죄지수가 가장 높은 참가자를 죽인다. 은진이는 되도록이면 이 게임을 오래 하고 싶다. 은진이가 이 게임에 정말 천재적으로 임하여 매번 최적의 선..
[백준 / BOJ] 2798 블랙잭 문제 출처 : www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 �� www.acmicpc.net N과 M이 주어지고, N개의 카드가 주어진다. 이 때, 카드 3개를 골랐을때, M을 넘지않으면서, M에 가장 근접한 수를 찾는 문제다. 풀이 N의 최댓값이 100이다. 100개의 칸에서 중복없이 3개를 선택하는 경우이므로, 100C3 만큼 반복해서, 시간초과가 나지않는다. 카드들중 임의의 카드 3개를 선택했을때 M에가장 근접한지 확인하고, 근접한다면 출력값을 update 해주고 다음으로 선택할 카드3..
[백준 / BOJ] 2233 사과나무 문제 출처 : www.acmicpc.net/problem/2233 2233번: 사과나무 문제 사과나무는 나무(tree)의 일종으로, 각각의 정점에 정확히 한 개의 사과가 있고, 모든 내부 정점(자식이 있는 정점)이 최소 두 개의 자식을 갖는 나무이다. 예를 들면 아래의 그림은 사과나무 www.acmicpc.net 정점의 개수와 벌레가 만드는 이진수를 입력받고, 정상적인나무를 최소화한상태로 썩은나무를 모두 없애는 정점을 구하는 문제다. 풀이 그래프 구조를 만들필요없이 해당노드의 등장 순서만 알고있다면 풀리는 문제다. 입력을 보면, 벌레가 만드는 이진수가 깊이우선탐색의 순서와동일한것을 알수있다. (해당 노드에서 끝까지 간후 더이상 갈수없을경우, 부모로 올라감) -이진수에 따라 자식과 부모관계를 만들어주기위해..
[백준 / BOJ] 3190 뱀 문제 출처 : www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. www.acmicpc.net N*N보드에서 뱀이 이동한다. 이때, 먼저 뱀의 머리를 움직인다. 뱀의 머리가 도착한 위치에 사과가 있다면, 꼬리는 그대로 있고 머리만 움직인다.(뱀의 몸의 길이가 한칸 늘어남) 아니라면, 몸의 길이를 줄여 꼬리가 위치한 칸을 비워준다. 풀이 처음에 문제 조건을 잘 읽지 않고 풀어서 힘들었다. 먼저 뱀의 몸길이를 늘려 머리를 다음칸에 위치시킨다.
[백준 / BOJ] 12100 2048 (Easy) 문제 출처 : www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net N * N 판이 주어졌을때, 최대 5번 합치면서 움직이며, 만들수있는 가장 큰 블록을 구하는 게임이다. 풀이 구현문제였다. - 3차원 temp배열을 만든다. (temp[i][j][cnt]) 이는 cnt번 움직였을때, i,j의 상태를 뜻한다. (연산 최소화) - check 배열을 만든다. cnt번 움직였을때, 최댓값이 check[cnt]에 저장된 값보다 작을경우, 리턴해..

티스토리툴바