728x90
반응형

BOJ/DP 64

[C/C++] 백준 - 5569번 : 출근 경로

https://www.acmicpc.net/problem/5569 5569번: 출근 경로 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대 www.acmicpc.net 예제 1의 경우 다음과 같은 5가지 경로가 있다. 전형적인 경로 탐색의 경우의 수를 파악하는 문제이다. 역시나 메모이제이션 - 동적계획법으로 실행 시간을 줄일 수 있다. 하지만 경로를 뻗어나가는데 있어 방향만 고려해야하는 것이 아닌 방향이 바뀌었을 경우 바로 다음 경우에는 방향 전환이 불가능하다. 즉, 방향 전환을 한 이후 최소 1번은 더 같은 방향으로 나아가야한다. 위 경우까지 고려하..

BOJ/DP 2022.02.17

[C/C++] 백준 - 18892번 : 가장 긴 증가하는 부분 수열 ks

https://www.acmicpc.net/problem/18892 18892번: 가장 긴 증가하는 부분 수열 ks N개의 정수로 이루어진 수열 A1, A2, ..., AN에서, 가장 긴 증가하는 부분 수열(LIS)의 길이를 L이라고 하자. LIS는 하나 또는 그 이상 있을 수 있다. 모든 LIS를 사전 순으로 정렬했을 때, K번째 오는 수 www.acmicpc.net 문제 N개의 정수로 이루어진 수열 A1, A2, ..., AN에서, 가장 긴 증가하는 부분 수열(LIS)의 길이를 L이라고 하자. LIS는 하나 또는 그 이상 있을 수 있다. 모든 LIS를 사전 순으로 정렬했을 때, K번째 오는 수열을 구해보자. 두 LIS Ai1, Ai2, ..., AiL와 Aj1, Aj2, ..., AjL이 있을 때, ..

BOJ/DP 2022.02.17

[C/C++] 백준 - 2240번 : 자두나무

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 문제 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다. 매 초마다, 두 개의 나무 중 하나의 나무에서 ..

BOJ/DP 2022.02.17

[C/C++] 백준 - 5557번 : 1학년

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는..

BOJ/DP 2022.02.14

[C/C++] 백준 - 14722번 : 우유 도시

https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 문제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 저번 축제에서 수많은 우유를 마셨지만 더욱 우유에 갈증을 느낀..

BOJ/DP 2022.02.10

[C/C++] 백준 - 12026번 : BOJ 거리

https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 문제 BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다. 스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다. BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다. 스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 ..

BOJ/DP 2022.02.08

[C/C++] 백준 - 1663번 : 최고의 팀 만들기

https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플 www.acmicpc.net 문제 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플레이어의 흑,백 능력치는 각각 1부터 100까지의 정수로 주어진다. 대회가 진행되는 동안 플레이어는 흑, 백 중 한 가지만으로 참여를 해야하며 팀의 전체 능력치는 흑 플레이어의 능력치를 합한것과..

BOJ/DP 2022.02.06

[C/C++] 백준 - 14430번 : 자원 캐기

https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 문제 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이..

BOJ/DP 2022.02.03

[C/C++] 백준 - 2876번 : 그래픽스 퀴즈

https://www.acmicpc.net/problem/2876 2876번: 그래픽스 퀴즈 오늘은 기초컴퓨터그래픽스의 퀴즈가 있는 날이다. 기다란 교실 안에는 N개의 책상이 한 줄로 늘어서 있는데, 각 책상당 두 명의 학생이 앉도록 되어있다. 모든 학생들은 그래픽스를 열심히 www.acmicpc.net 문제 오늘은 기초컴퓨터그래픽스의 퀴즈가 있는 날이다. 기다란 교실 안에는 N개의 책상이 한 줄로 늘어서 있는데, 각 책상당 두 명의 학생이 앉도록 되어있다. 모든 학생들은 그래픽스를 열심히 공부했지만, 말도 안되는 난이도에 질려 포기하고 말았다. 한편 교수님은 각 학생들의 얼굴만 보고도 이 학생이 받아야 할 그레이드를 정확히 알아낼 수 있다. 교수님은 그래픽스 과목을 가르치는 만큼 자신의 미적 감각을 살..

BOJ/DP 2022.02.03

[C/C++] 백준 - 21317번 : 징검다리 건너기

https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 문제 심마니 영재는 산삼을 찾아다닌다. 산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다. 마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다. 점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다. 각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너..

BOJ/DP 2022.02.02
728x90
반응형