본문 바로가기

알고리즘

 (151)
[백준 / BOJ] 19538 루머 문제 출처 : https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net N명이 사람이 있다. 이 N명의 사람은 어떠한 루머를 자신과 연관된 주변인중 절반이상이 믿는다면 자신또한 그 루머 믿는다. 이때, 모든 사람이 루머를 믿기위해서 걸리는 시간을 구하는 프로그램을 구하는 문제다. 충분히 많은 시간이 지나도 루머를 믿지 않을 경우 -1을 출력하면된다. 소스코드 기본적인 다익스트라 문제였다. 각 사람이 루머를 믿기시작..
[백준 / BOJ] 19542 전단지 돌리기 문제 출처 : https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이는 KENNYSOFT위치에서 시작하여 전단지를 다 돌리고 KENNYSOFT로 돌아오며, 이때, 전단지를 던져 거리가 D미만인 노드에 전단지를 한번에 돌릴 수 있다. 현민이가 전단지를 모든 노드에 돌리고 KENNYSOFT로 돌아오는 최단 경로를 구하는 문제다. 풀이 트리탐색으로 풀리는 문제였다. 1년전에 풀려고..
[백준 / BOJ] 15900 나무 탈출 문제 출처 : https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 트리의 정점의 개수 N, N-1개의 줄에 거쳐 간선의 정보가 주어진다. 각 간선의 끝(리프노드)에 게임 말이 존재한다. 성원이와 형석이는 이 게임 말을 한턴에 한번씩 부모노드로 움직이는 방식으로 게임을 진행하려고한다. 게임 말은 루트노드에 도착하면 사라지며, 이 과정을 반복하다 자신의 턴에 더 이상 고를수있는 게임 말이 없다면, 그 사람은 게임에서 패배한다. 항상 성원이가 먼저 시작..
[백준 / BOJ] 10885 수열의 장인 문제 출처 : https://www.acmicpc.net/problem/10885 10885번: 수열의 장인 승현이는 수열을 찾는 사람들을 위해 길이가 N 인 수열 a1, a2, ··· , aN을 만드는 일을 하고 있다. 승현이는 경력이 짧아서 각 원소가 -2 이상 2 이하의 정수인 수열만 만들 수 있고, 그래서인지 수 www.acmicpc.net 길이 N의 수열이 주어진다. 수열의 각 수는 -2, -1, 0, 1 2로 이루어져있으며, i번째 수열을 Ai, j번째 수열을 Bj라 하자. (i
[백준 / BOJ] 10881 프로도의 선물 포장 (Java) 문제 출처 : https://www.acmicpc.net/problem/10881 10881번: 프로도의 선물 포장 프로도는 네오에게 줄 생일 선물을 세 개 샀다. 이 세 개의 선물은 직사각형 모양의 선물 상자에 각각 하나씩 담겨 있다. 프로도는 이 선물들을 적당한 크기의 직사각형 포장 상자에 넣어 포장하 www.acmicpc.net 프로도는 네오에게 줄 생일 선물을 세 개 샀다. 선물 세 게를 N*M 크기의 상자에 적절히 담을려고한다. (모든 상자의 면은 서로 수평되어야 하며, 상자는 90도 회전가능하다.) 이때, 상자의 사이즈를 가장 작게하는 프로그램을 구하는 문제다. 풀이 상자가 최대 3개이고, 테스트케이스도 10,000이므로 완전탐색으로 풀수있는 문제다. 다만, 구현이 까다로웠는데, 상자의 크기가..
[백준 / BOJ] 1561 놀이 공원 문제 출처 : https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 놀이공원에 N명의 사람과, M개의 놀이기구가 있다. M개의 놀이기구는 각각 운행시간이 있으며, N명의 사람은 놀이기구를 "현재 탑승가능한 놀이기구중 빠른번호 순서"로 탑승하려고한다. 이때, 마지막사람이 탑승할 놀이기구의 번호를 출력하는 문제다. 풀이 처음 문제를 봤을때는, 스킵하는 방식의 dp를 이용한 문제일거라고 생각했는데, N이 최대 2,00..
[백준 / BOJ] 18430 무기 공학 (Java) 문제 출처 : https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net N*M그리드가 주어진다. 길동이는 N*M그리드의 각 칸을 적절히 잘라서 부메랑을 만들어야한다. 길동이가 만들수있는 부메랑들의 크기의 총합을 가장 크게하는 프로그램을 만드는 문제다. 풀이 N과 M이 5가 최대이므로 완전탐색으로 풀수있는 문제였다. 백 트래킹으로 구현한 전형적인 백트래킹 문제다. 구현중 주의할점은 아래와 같다. 현재 위치를 y,x라 했을때, 다음에 탐색..
[백준 / BOJ] 1244 스위치 켜고 끄기 문제 출처 : https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 1번부터 N번까지 총 N개의 스위치가 있다. 쿼리가 주어졌을때, 최종 스위치 상태를 출력하는 문제다. 문제에서 주어진 그대로 구현하면 되는문제다. 출력이 20이 넘어갈때, 줄 바꿈을 해줘야하는점만 주의하면 어렵지않게 풀리는 문제였다. 주요 소스코드 private void girl(int num){ int left = num; int right = num; while(left >..

티스토리툴바