알고리즘 풀이
-
백준(BOJ) 6359번 만취한 상범알고리즘 풀이/백준(Boj) 2019. 8. 7. 14:41
문제 : https://www.acmicpc.net/problem/6359 문제서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고..
-
백준(BOJ) 2110번 공유기 설치알고리즘 풀이/백준(Boj) 2019. 8. 6. 17:38
문제 : https://www.acmicpc.net/problem/2110 문제도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 나의 풀이: 집들의 간격을 오름차순으로 정렬한다. 그 후 최소 간격수와 최대 간격수를 정한다. 최소 간격수와 최대 간격수 사이에..
-
백준(BOJ) 7562번 나이트의 이동알고리즘 풀이/백준(Boj) 2019. 8. 6. 03:26
문제 : https://www.acmicpc.net/problem/7562 문제체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 나의 풀이: 큐에 pair 를 통하여 앞에 값에는 y값과 x값을 , 뒤에 값은 이동 횟수로 지정하여 0을 넣고 1씩 증가하여 도착 시 이동 횟수를 저장 하였다. 코드 ( C++ ) #include #include #include #include using namespace std; int l;int x, y, dx, dy; // 나이트의 이동 방향int my[8] = { 2,1,-2,-1,-1,-2,1,2 };int mx[8] = ..
-
시계 맞추기알고리즘 풀이/알고리즘 해결전략 연습 2019. 8. 4. 20:17
문제 : https://algospot.com/judge/problem/read/CLOCKSYNC 문제그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.00, 1, 213, 7, 9, 1124, 10, 14, 1530, 4, 5, 6, 746, 7, 8, 10, 125..
-
백준(BOJ) 1987번 알파벳알고리즘 풀이/백준(Boj) 2019. 8. 4. 17:50
문제 : https://www.acmicpc.net/problem/1987 문제세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 나의풀이: 기존 전형적인 DFS에 alphabet 배열을 매개 변수로 받아서 같은 알파벳이 나왔을 경우에는 가지 못..
-
백준(BOJ) 1019번 책 페이지알고리즘 풀이/백준(Boj) 2019. 8. 3. 23:33
문제: https://www.acmicpc.net/problem/1019 문제지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오. 풀이: // 처음 시도 시간 초과 #include #include using namespace std;int N;int check[10];int main(){ios_base::sync_with_stdio(0);cin.tie(0);memset(check, 0, sizeof(check));cin >> N;for (int i = 1; i > n;solve(1, n, 1);for (int i = 0; i < 10; ++i)cout
-
백준(BOJ) 1449번 수리공 항승알고리즘 풀이/백준(Boj) 2019. 8. 3. 03:21
문제: https://www.acmicpc.net/problem/1449 문제항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.항승이는 길이가 L인 테이프를 무한개 가지고 있다.항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능..
-
감시 카메라 설치알고리즘 풀이/알고리즘 해결전략 연습 2019. 8. 3. 02:18
문제 : https://algospot.com/judge/problem/read/GALLERY 코드( C ++ ) 종만북 참조 문제전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모 프로게이머의 얼굴로 합성하겠다는 것입니다. 미술관의 관장을 맡고 있는 재하는 이와 같은 사태를 방지하기 위해 감시 카메라를 설치하기로 마음먹었습니다. 미술관은 여러 개의 갤러리와 이들을 연결하는 복도로 구성되어 있으며, 한 갤러리에 감시 카메라를 설치하면 이 갤러리와, 복도로 직접 연결된 갤러리들을 감시할 수 있습니다. 모든 갤러리를 감시하기 위해 필요한 최소 감시 카메라의 수는 몇 개일까요?미술관은 한 번 관람한 갤..