본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 1941 소문난 칠공주 문제 출처 : www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 5*5그리드에 학생들의 파가 주어진다. (이다솜파 : S, 임도연파 : Y) 이다솜은 자신의 파를 늘리기위해 소문난 칠공주를 결성하기로했다. 칠공주가 되기위해선 3가지 조건이 필요한데, 1. 칠공주에 속하는 학생들은 서로 인접해있어야한다. 2. 7명의 학생으로 구성되어야한다. 3. 이다솜파보다 임도연파가 더 많아야한다. 이때, 소문난 칠공주를 결성하는 모든 경우의수를 구하는 문제다. 풀이 푸는데 2일..
[백준 / BOJ] 16724 피리 부는 사나이 문제 출처 : www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net N*M지도가 있고, 그 위에 영과일 회원들이 있다. 지도의 각 칸에는 U,D,L,R 이 쓰여있는데, (순서대로 위, 아래, 왼쪽, 오른쪽) 성우가 피리를 불기 시작하면, 영과일 회원은 자기 발 아래의 방향에 맞게 이동한다. 재훈이는 영과일 회원의 안전을 위해 SAFE ZONE을 설치할려고한다. 영과일 회원이 어디에 있던지 항상 SAFE ZONE으로 들어갈수있도록..
[백준 / 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 문제 해결 강의를 신청한 학생들은 텀 프로젝트를 수행해야한다. 각 학생들마다 팀을 하고싶은 학생이 다르고, 한 학생이 한명의 학생만 선택할수있다. 학생들의 팀원선택이 사이클을 이루면 해당 학생들은 팀을 이뤘다고할때, 팀을 이루지못한 학생들의 수를 구하는 문제다. 풀이 학생들의 사이클을 찾으면 되는 문제인데, 시간초과를 조심해야한다. 풀이의 핵심은 한 학생을 기준으로 그룹을 찾을때마다, 해당 그룹안에 포..

티스토리툴바