전체 글

백준 11049 - 행렬 곱셈 순서https://www.acmicpc.net/problem/11049문제크기가 NxM인 행렬 A, MxK인 B를 곱할 때 필요한 곱셈의 연산 수는 총 NxMxK번행렬 N개를 곱하는데 필요한 곱셈의 연산 수는 행렬을 곱하는 순서에 따라 달라짐ex. A의 크기 5x3, B의 크기 3x2, C의 크기 2x6인 경우 행렬 곱 ABC- (AB)C_AB를 먼저 곱하고 C를 곱하는 경우: 5x3x2 + 5x2x6 = 30 + 60 = 90- A(BC)_BC를 먼저 곱하고 A를 곱하는 경우: 3x2x6 + 5x3x6 = 36 + 90 = 126입력 첫째 줄: 행렬의 개수 N (1 둘째 줄 ~ N개의 줄: 행렬의 크기 r, c (1 항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어짐..

백준 2042 - 구간 합 구하기https://www.acmicpc.net/problem/2042문제어떤 N개의 수가 주어져 있음/ 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려고 함ex. 1, 2, 3, 4, 5 -> 3번째 수를 6으로 바꾸고 2 ~ 5까지의 합 => 17입력첫째 줄: 수의 개수 N (1 , 수의 변경이 일어나는 횟수 M (1 둘째 줄 ~ N + 1번째 줄: N개의 수N + 2번째 줄 ~ N + M + K + 1번째 줄: 세 개의 정수 a, b, ca가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 합 구하여 출력(1 출력: 첫째 줄부터 K줄에 걸쳐 구한 구간의 합 출력 ($-2^{63}$ 풀이세그먼트 트리(Segment..

백준 1700 - 멀티탭 스케줄링https://www.acmicpc.net/problem/1700문제ex. 3구 멀티탭 사용 순서키보드 -> 헤어드라이기 -> 핸드폰 충전기 -> 디지털 카메라 충전기 -> 키보드 -> 헤어드라이기=> 키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전 핸드폰 충전기 플러그를 빼는 것이 최적 -> 1번만 빼면 됨입력첫 줄: 멀티탭 구멍의 개수 N (1 두 번째 줄: 전기용품의 이름 출력: 하나씩 플러그를 빼는 최소의 횟수풀이가장 나중에 다시 사용되거나 아예 안 쓰이는 것 제거`Set set = new HashSet`: 현재 멀티탭에 꽂혀 있는 전기용품들`cnt`: 플러그를 뽑은 횟수 (정답) `int cur ..

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 둘째 ..