작심 24/7

11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비트마스크를 이용해 집합을 표현해서 푸는 문제이다. S {1, 4, 5} = 11001 이렇게 S에 들어가 있는 원소는 1로, 없으면 0으로 생각하면 된다. 연산의 핵심은 1 M; for (int i = 0; i > order; if (!(order == "all" || order == "empty")) cin >> x; // all이나 empty는 x를 받을 필요 없음 if (order == "add") S |= 1

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net ▷다른 방식 풀이 보러가기 최대 10번 움직여서 빨간 구슬을 빼내야 하므로 상, 하, 좌, 우로 기울이는 순서를 1~10 까지 중복 순열로 지정한다. 대신, 같은 방향이 연속되지 않게 한다. ex) 1번 움직일 경우 가능한 순서 : 1) 상(↑) 2) 하(↓) 3) 좌(←) 4) 우(→) 2번 움직일 경우 가능한 순서 : 1) 상(↑) 하(↓) 2) 상(↑) 좌(←) 3) 상(↑) 우(→) 4) 하(↓) 상(↑) ..

1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 예를 들어, N=4이면, 문방구에서 파는 www.acmicpc.net 가장 큰 수를 만들기 위한 우선순위는 아래와 같다. 1. 자릿수가 최대한 길어야 한다. 2. 맨 앞자리부터 최대한 큰 수가 들어가 있어야 한다. 먼저 1번을 만족하려면 무조건 숫자를 많이 모아야 하기 때문에 비용이 가장 적은 숫자를 최대한 많이 산다. 이때, 비용이 가장 적은 숫자가 0이라면 맨 앞자리에 0이 오면 안 되므로 비용이 두 번째로 적은 숫자를 하나 사서 맨 앞자리에 배치한 다음에 나머지는 비용이 가장 적은 숫자로 채운다. 2번을 만족하기 위해..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 최단 거리를 구하는 문제이므로 BFS를 쓰는 게 적합하다. 일단 큐에는 x, y좌표 뿐만 아니라 현재까지의 이동 횟수, 이전에 벽을 부쉈는지의 여부 도 저장해주어야 한다. 벽을 한 번만 부술 수 있기 때문에 이전에 벽을 부순 적이 있으면 그 루트는 앞으로 벽을 뚫고 지나가지 못 한다. 그리고 방문 체크를 해줄 때 벽을 한 번 부순 경우와 벽을 부수지 않은 경우 두 가지로 나누어서 체크해주어야 하기 때문에 3차원 배열 visited를 사용..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 시간 초과와의 싸움이었다. N번만큼 for문을 돌면서 visited 배열을 초기화해줬는데 이게 시간 초과의 주된 원인이라고 한다. 그래서 초기화는 테스트 케이스마다 한 번씩만 해주고 재귀에서 빠져나올 때마다 visited 배열의 값을 false로 바꿔주는 방식으로 대체하였다. 1. 각 원소는 무조건 어떤 원소를 가리킨다. 마지막엔 무조건 사이클로 끝나게 된다. 2. 한 번 방문한 곳은 visited, 예전에 검사가 끝난 곳은 done으로 표시할 때, done으로 표시..

2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net stack에 탑의 위치, 높이를 저장한 후 stack의 top 값 (= 이전 탑의 길이) 현재 탑의 길이 가 될 때까지 (= 수신할 수 있는 탑이 나올 때까지) 계속 pop 해버린다. → 수신할 수 있는 탑을 만나면 그 탑의 위치를 출력하고 현재 탑의 정보를 저장한다. → stack이 empty 상태가 되면..

3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net 1. 교환 전에 먼저 모든 행과 열을 한 번씩만 탐색해주며 최댓값을 찾는다. 2. 사탕을 교환하고 그때 값이 바뀌는 행과 열에서 가장 긴 연속 부분을 탐색한 뒤 교환 전으로 다시 되돌려 놓는 방식을 반복해서 최댓값을 찾는다. 교환은 두 가지 종류를 해줘야 하는데, 첫 번째는 행 교환이다. 이때 값이 바뀌는 열 2개랑 행 1개를 탐색해서 최댓값을 업데이트한다. 두 번째는 열 교환이다. 마찬가지로 이때 값이 바뀌는 열 1개랑 행 2개를 탐색해서 최댓값을 업데이트한다. import java.util.Scanner; public class BOJ_3085_사탕게임 { static int max =..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net graph[정점 A] = (정점 B, A→B 비용) 으로 값을 입력받은 후 dist[i] = K→i 비용 을 저장한다. 처음에는 모두 무한대로 저장해 두고 K→K일 때만 0을 저장해준다. 우선순위 큐 pq는 비용을 기준으로 오름차순 정렬된다. 제일 처음엔 시작점 K와 K→K 비용 0을 넣어준다. pq의 top에 있는 정점을 mid라 표현할 때, mid에서 바로 갈 수 있는 정점들 to를 탐색해주며 시작점 K→to 비용보다 시작점 K→m..