개발조아

문제 링크 : https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 이분 탐색으로 풀었다. 최대 HP는 모든 칸이 다 몬스터이고 모든 애들의 공격력과 체력이 1백만이라 했을 때 123456*1백만*1백만이다. 1~최대 HP까지에서 이분탐색으로 hp찾아보자. hp를 선택했으니 시뮬레이션 돌려보자. 만약 돌린 결과가 False가 나온다면 선택한 hp로는 부족하다는 뜻이다. 그러므로 m..

문제 링크 : https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net BFS + 구현 문제이다. 알고리즘 자체는 어렵지 않으나 상태값을 잘못 지정하여 틀리고 있었다. 문제는 간단하다. 맵에 특정칸에는 다른 칸의 조명을 켤수 있는 스위치가 있고, 주인공은 상하좌우로 조명이 켜진 칸으로만 이동이 가능하다. 한 스위치로 여러개의 조명을 컨트롤 가능하고 한 조명이 여러 스위치에 의해 컨트롤이 가능하다. 이..

문제 링크 : https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 각 노드에서 출발하여 정해진 가중치 이내로 갈 수 있는 노드들이 가지고 있는 값의 합의 최대값을 구하는 문제이다. 모든 노드에서 각 노드로 최단거리를 구해서 그 길이가 m 이하인 것들의 아이템수의 합을 구하고 그중 최대값을 구하면 된다. 모든 노드에 대해서 최단거리는 플로이드와샬과 다익스트라로 해결할 수 있다. 해당 문제는 노드의 개수가 최대 100개 이므로 플로이드와샬로 해결 가능하다...

문제 링크 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net BFS, 백트레킹, 조합 다 써볼수 있는 좋은 문제라고 생각한다. 문제는 비교적 간단하다. 요약하면 아래와 같다. 배양액의 종류는 두개이고 이 배양액을 놓을 수 있는 칸은 최대 10개 이하로 정해져있다. 배양액을 넣을 수 있는 칸에 주어진 배양액 전부 적절히 분배하고 확산시킨다. 이때 배양액은 동서남북 방향으로 퍼지며 물로는..

문제 링크 : https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 처음에는 그날그날 모든 칸의 크기를 구해서 넣어줬다. 그랬더니 시간이 너무 오래 걸려서 다시 생각해봤다. 모든 애벌래는 1부터 시작하고 첫번째 행, 첫번째 열을 제외하고는 그칸에서 왼쪽, 오른쪽, 왼쪽위칸의 값중 가장 큰값이 해당 칸의 크기가 된다. 그렇기 때문에 그냥 첫행, 첫열의 값만 구해주면 된다. 입력으로 들어온 값은 애벌레들이 자라는 정도를 왼쪽 제..

문제 링크 : https://www.acmicpc.net/problem/22234 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 은행에서 업무를 라운드 로빈 방식으로 처리한다. OS 스케쥴링 정책 중 라운드 로빈 스케쥴링이다. 간단히 설명하면 프로세스들 사이에 우선순위를 두지 않고 들어온 순서대로 처리하지만 공평하게 CPU를 사용하기 위해 시간단위(Time Quantum) 만큼만 CPU를 할당받아 수행한다. 이후 작업이 남아있다면 다시 대기열의 맨 뒤로 가서 대기한다. 문제의 알고리즘도 이 방식으로 진..

문제 링크 : https://www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 문제를 잘 이해를 못해서 좀 고민했다. 가장 안전한 길이란 모든 칸에서 나무와 거리의 최솟값이 가장 큰 경로이다. 이 부분에서 최솟값이 가장 큰 경로라길래 최솟값이 가장 크면 가장 작은 값인가 큰값인가 헷갈렸었다. 아주 멍청이 같은 생각이었다. 모든 점에서 나무까지의 거리 중 최소값을 찾아서 저장하고 이동 중에 이 거리가 큰값을 선택해서 가면 된다. 모든 점에서 나무까지의 거리는 BFS로 돌..

문제 링크 : https://www.acmicpc.net/problem/1325