전체 글

1516 - 게임 개발https://www.acmicpc.net/problem/1516문제게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 최소 시간 이용어떤 건물을 짓기 위해 다른 건물을 먼저 지어야 할 수 있음ex. 스타크래프트: 벙커 짓기 위해서는 배럭을 먼저 지어야 함여러 개의 건물 동시에 지을 수 있음자원 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않음입력첫째 줄: 건물의 종류 수 N (1 다음 N개 줄: 각 건물을 짓는데 걸리는 시간, 건물을 짓기 위해 먼저 지어야 하는 건물들의 번호(건물의 번호 1 ~ N, 각 줄은 -1로 끝남/ 건물을 짓는데 걸리는 시간 출력: N개의 각 건물이 완성되기까지 걸리는 최소 시간풀이`graph[..

6549 - 히스토그램에서 가장 큰 직사각형https://www.acmicpc.net/problem/6549문제히스토그램: 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수 있음입력각 테스트 케이스는 한 줄로 이뤄져 있고, 직사각형 수 n이 가장 처음으로 주어짐 (1 히스토그램에 있는 직사각형의 높이인 n개의 정수 h_1, ..., h_n (0 (왼쪽부터 오른쪽 순서대로)모든 직사각형 너비 1, 입력 마지막 줄 0)출력: 각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이 출력풀이`stack`: 인덱스 저장하는 스택높이가 증가하는 순서로 인덱스 유지`max`: 최대 직사각형 넓이 오른쪽으로 이동하며 스택 처리`heigh..

14499 - 주사위 굴리기https://www.acmicpc.net/problem/14499문제크기 NxM인 지도/ 오른쪽은 동쪽, 위쪽은 북쪽지도의 좌표 (r, c) -> r: 북쪽으로부터 떨어진 칸의 개수, c: 서쪽으로부터 떨어진 칸의 개수주사위는 지도 위에 윗 면이 1, 동쪽을 바라보는 방향이 3인 상태/ 놓여져 있는 곳 좌표 (x, y)/ 가장 처음에는 모든 면 0지도 각 칸에 정수 하나씩 쓰여 있음주사위 굴렸을 때, 이동한 칸에 쓰여 있는 수 0 -> 주사위 바닥면에 쓰여 있는 수가 칸에 복사/ 0이 아닌 경우 -> 칸에 쓰여 있는 수 -> 주사위 바닥면으로 복사, 칸에 쓰여 있는 수 0이 됨입력첫째 줄: 지도 세로 크기 N, 가로 크기 M (1 , 주사위 놓은 곳 좌표 x, y (0 둘째 ..

백준 14891 - 톱니바퀴https://www.acmicpc.net/problem/14891문제총 8개 톱니 가지고 있는 톱니바퀴 4개/ N극 or S극 중 하나 가지고 있음총 K번 회전시키는데 서로 맞닿은 톱니 극이 다르면 반대방향으로 회전입력첫째 줄: 1번 톱니바퀴 상태둘째 줄: 2번 톱니바퀴 상태셋째 줄: 3번 톱니바퀴 상태넷째 줄: 4번 톱니바퀴 상태(8개의 정수로 12시 방향부터 시계방향 순서대로 주어짐/ N : 0, S : 1)다섯째 줄: 회전 횟수 K (1 다음 K개 줄: 회전시킨 방법 순서대로 주어짐 (첫 번째: 회전시킨 톱니바퀴 번호, 두 번째: 방향/ 1 : 시계, -1 : 반시계)출력: 총 K번 회전시킨 이후에 네 톱니바퀴의 점수 합1번 톱니바퀴의 12시 방향이 N -> 0점 / S..

백준 1043 - 거짓말https://www.acmicpc.net/problem/1043문제파티에서 이야기를 말할 때, 있는 그대로 말하거나 과장해서 말함거짓말쟁이로 알려지기 싫기 때문에 진실을 아는 사람이 파티에 오면 진실을 이야기 함어떤 사람이 파티에서 진실을 듣고, 또 다른 파티에서 과장된 이야기를 들으면 거짓말쟁이로 알려짐입력첫째 줄: 사람 수 N, 파티 수 M (1 둘째 줄: 이야기의 진실 아는 사람 수와 번호 (0 (진실을 아는 사람 수 먼저 주어지고 그 개수만큼 사람들 번호(1 ~ N) 주어짐)셋째 줄 ~ M개 줄: 각 파티마다 오는 사람 수, 번호 (1 출력: 거짓말쟁이로 알려지지 않으면서 과장된 이야기를 할 수 있는 파티 개수의 최댓값풀이Union-Find (같은 파티 참석 -> 같은 그..

백준 5214 - 환승https://www.acmicpc.net/problem/5214문제하이퍼튜브 하나는 역 K개를 서로 연결입력첫째 줄: 역의 수 N, 서로 연결하는 역의 개수 K, 하이퍼튜브 개수 M (1 M개 줄: 하이퍼튜브 정보/ 총 K개 숫자 - 하이퍼튜브가 서로 연결하는 역의 번호출력: 1번역에서 N번역으로 가는데 방문하는 역의 개수 최솟값 / 갈 수 없다면 -1풀이역: 1 ~ N하이퍼튜브: N + 1 ~ N + M`int tube = N + i` `dist[i]`: 1번 역에서 i번 노드까지 최단 이동 횟수`dist[i] = -1`: 아직 방문 X`dist[1] = 1`: 1번 역은 1번 방문 처리int[] dist = new int[N + M + 1];Arrays.fill(dist, -1..