백준

[백준] 7579 - 앱 (자바 Java)

[Gold III] 앱 - 7579 문제 링크 성능 요약 메모리: 17628 KB, 시간: 156 ms 분류 다이나믹 프로그래밍(dp), 배낭 문제(knapsack) 문제 설명 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다. 하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라..

[백준] 17244 - 아맞다우산 (자바 Java)

[Gold II] 아맞다우산 - 17244 문제 링크 성능 요약 메모리: 99772 KB, 시간: 360 ms 분류 너비 우선 탐색(bfs), 비트마스킹(bitmask), 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, ..

[백준] 9466 - 텀 프로젝트 (자바 Java)

[Gold III] 텀 프로젝트 - 9466 문제 링크 성능 요약 메모리: 303204 KB, 시간: 1344 ms 분류 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는..

[백준] 17281 - ⚾ (자바 Java)

[Gold IV] ⚾ - 17281 문제 링크 성능 요약 메모리: 295764 KB, 시간: 908 ms 분류 브루트포스 알고리즘(bruteforcing), 구현(implementation) 문제 설명 ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한..

[백준] 17136 - 색종이 붙이기 (자바 Java)

[Gold II] 색종이 붙이기 - 17136 문제 링크 성능 요약 메모리: 22020 KB, 시간: 344 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing) 문제 설명 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 ..

[백준] 1931 - 회의실 배정 (자바 Java)

[Silver I] 회의실 배정 - 1931 문제 링크 성능 요약 메모리: 165876 KB, 시간: 1136 ms 분류 그리디 알고리즘(greedy), 정렬(sorting) 문제 설명 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 ..

[백준] 2206 - 벽 부수고 이동하기 (자바 Java)

[Gold IV] 벽 부수고 이동하기 - 2206 문제 링크 성능 요약 메모리: 339388 KB, 시간: 976 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸..

[백준] 16235 - 나무 재테크 (자바 Java)

[Gold III] 나무 재테크 - 16235 문제 링크 성능 요약 메모리: 142464 KB, 시간: 1044 ms 분류 자료 구조(data_structures), 구현(implementation), 시뮬레이션(simulation) 문제 설명 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해..

[백준] 17135 - 캐슬 디펜스 (자바 Java)

[Gold III] 캐슬 디펜스 - 17135 문제 링크 성능 요약 메모리: 32012 KB, 시간: 312 ms 분류 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 구현(implementation), 시뮬레이션(simulation) 문제 설명 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다...

[백준] 17471 - 게리맨더링 (자바 Java)

[Gold IV] 게리맨더링 - 17471 문제 링크 성능 요약 메모리: 14924 KB, 시간: 136 ms 분류 너비 우선 탐색(bfs), 브루트포스 알고리즘(bruteforcing), 조합론(combinatorics), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 수학(math) 문제 첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다. 셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다. 구역 A가 구역 ..