본문 바로가기

전체 글

 (333)
[백준 / BOJ] 1937 욕심쟁이 판다 문제 출처 : www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net N*N크기의 대나무 숲에있는 판다는 한 지역의 대나무를 다 먹으면 상하좌우중 한 방향으로 움직일수있다. 단, 이때 움직인곳은 전 지역보다 대나무가 많아야한다. 풀이 9달전에 풀다가 틀렸었는데, 알고리즘 공부를 더 하고서야 맞췄다. (9달전에는 바텀업 구현을 못해서 풀지 못했음) DFS와 DP를 합친 문제다. 1. (i ~ N) (j ~ N) 까지 전부다 돌려준다. 2. (i,j)점에서 시..
[백준 / BOJ] 1932 정수 삼각형 문제 출처 : www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 정수 삼각형을 입력받았을때, 합이 최대가 되는경로를 찾는문제이다 (각 층에선 한 정수만 더 할수있음) 예를들어 을 입력받으면, 최대경로는 1 -> 3 -> 6 = 10이 된다. 풀이 N을 입력을 받고 정수삼각형의 각 정수 입력마다 최댓값을 찾아줬다. 위 정수삼각형에서 규칙을 찾을수있는데, 1층에는 정수가 1개, 2층에는 정수가 2개 ,3층에는 3개...순으로 늘어..
[백준 / BOJ] 5397 키로거 [이중 연결 리스트] 문제 출처 : www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거� www.acmicpc.net 주어진 문자열에서 비밀번호를 찾아 출력하는 알고리즘이다. '' 를 입력받으면 커서를 한칸 오른쪽으로 움직인다. '-' 를 입력받으면 커서뒤의 글자를 지운다. 예를들어, A
[백준 / 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..

티스토리툴바