본문 바로가기

분류 전체보기

 (340)
[백준 / BOJ] 16562 친구비 문제 출처 : www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 학생수N과 학생들의 친구관계수 M, 현재 가지고 있는 돈 K가 주어진다. 학생들과 친구를 하기위해선 일정한 금액을 내야한다. 준석이는 자신이 갖고있는 돈 K로 모든 학생과 친구를 할수없을수도있기때문에, 친구의 친구는 친구다 를 이용하기로했다. 이때, 준석이가 모든 학생과 친구를 하기위해 들어가는 최소비용을 출력하는 문제다. 모든 학생과 친구를 할수없으..
[백준 / BOJ] 2342 Dance Dance Revolution 문제 출처 : www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 승환이는 DDR게임을 할려고한다. 중앙, 위, 왼쪽, 아래, 오른쪽 순서로 0, 1, 2, 3, 4 라고 할때, 승환이가 눌러야할 방향이 순서대로 주어진다. 한 위치에서 다른 위치로 발을 이동시킬때드는 힘의 크기가 다를때, 모든 방향을 누를때 드는 최소힘의 크기를 구하는 문제다. 풀이 BFS나 DP로 풀리는 문제다. 왼쪽발을 움직여서 해당 숫자를 누르는게 당장은 ..
[백준 / BOJ] 1644 소수의 연속합 문제 출처 : www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 자연수 N이 주어진다. 연속된 소수들을 더해서 자연수 N을 더하는 경우의수를 구하는 문제다. 풀이 '연속된 소수들을 이용해서 N을 만들어야 한다'는 조건이 있기때문에, 투포인터를 이용해 풀수있다. 소수만을 가지고 N을 만들어야 한다. 매번 해당 숫자가 소수인지 판단하면 너무 오래걸리기 때문에, 에라스토테네스의 체를 이용해 미리 소수들을 구해서 벡터에 넣어줬다. 연속된 소수들의 시작idx와 끝idx를 나타내는 left, right를 선언해줬다. 연속된 소수들의 합 S = (vec[left] + vec[left + 1]..
[백준 / BOJ] 13460 구슬 탈출 2 문제 출처 : www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 보드의 가로, 세로의 길이가 주어지고, 두 구슬 R,B의 위치가 주어진다. 보드를 기울여 구슬을 동서남북으로 움직일수있다. 단, 한번 움직이면, 벽, 다른 구슬, 구멍을 만날때까지 기울인 방향으로 움직여야한다. R구슬만 탈출시키는 최소한의 이동 횟수를 구하면 된다. 풀이 시키는대로 하면되는 구현문제다. BFS알고리즘을 이용해 풀었다. - check..
[백준 / BOJ] 12852 1로 만들기 2 문제 출처 : www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 숫자 N이 주어졌을때, 1. 나누기 2 2. 나누기 3 3. 빼기 1 을 적절히 사용하여 최소한의 연산으로 1을 만드는 문제다. 풀이 너비우선 탐색이기때문에, 항상 최소경로가 가장 먼저나오는 BFS를 사용해 최소 연산을 찾아주면된다. 경로는, 의 check배열에 {연산횟수, 이전 숫자}형태로 저장해준다. 이전숫자가 없을경우(처음숫자) 이전숫자 위치에 -1을 저장해놓는다. (연산횟수보다 작은 연산횟수가 나오지않는다면 check배열이 업데이트 되지않으므로 항상 성립한다) 배열을 따라 1부터 올라가며 경로를..
[백준 / BOJ] 9466 텀 프로젝트 문제 출처 : www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 해결 강의를 신청한 학생들은 텀 프로젝트를 수행해야한다. 각 학생들마다 팀을 하고싶은 학생이 다르고, 한 학생이 한명의 학생만 선택할수있다. 학생들의 팀원선택이 사이클을 이루면 해당 학생들은 팀을 이뤘다고할때, 팀을 이루지못한 학생들의 수를 구하는 문제다. 풀이 학생들의 사이클을 찾으면 되는 문제인데, 시간초과를 조심해야한다. 풀이의 핵심은 한 학생을 기준으로 그룹을 찾을때마다, 해당 그룹안에 포..
[백준 / BOJ] 2056 작업 문제 출처 : www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net N개의 수행할 작업과, 각 작업을 수행하는데 걸리는 시간이 주어진다. 작업에는 선행관계가 있고, 각 작업을 수행하기위해선, 해당 작업의 선행작업을 수행해야한다. 이때, 모든 작업을 수행하는데 걸리는 최소시간을 구하는 문제다. 풀이 재귀와 메모이제이션으로 풀리는문제다. 현재 작업 A를 수행해야하고 A의 선행 작업이 B,C,D라고 할때, B,C,D가 걸리는 수행시간중 최댓값을 가져와서 A가 ..
[백준 / BOJ] 1806 부분합 문제 출처 : www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 수열의 길이 N과 만들어야할 최소 수 S가 주어진다. 수열의 각 원소들의 합이 S이상이 되는 최소 길이를 구하는 문제다. 풀이 N이 최대 10만까지 가기때문에, 최악의 경우 100001 * 50000번 반복해서 시간초과가 난다. 투포인트로 풀었는데, 수열의 인덱스를 나타내는 변수 p1, p2를 선언한다. p1 ~ p2의 합이 S보다 커질때까지 p2를 증가시킨다. 이때, 합이 S보다 ..

티스토리툴바