BOJ

    BOJ 14889 · 스타트와 링크

    알고리즘 분류 : 브루트 포스 두 팀으로 나눠서 두 팀의 능력치 차에 대한 최솟값을 구하는 문제다. 재귀 함수를 이용하여 구현할 수 있다. 재귀 함수는 두 팀으로 나누는 과정에 이용한다.팀을 구분하는 체크 배열 c를 둔다. 팀의 구분은 true와 false로 한다.재귀 함수 종료 조건은 인덱스가 N을 벗어났을 때이거나 팀 인원이 N/2 명이 되었을 때이다.팀 능력치의 총합은 N^2 for 문으로 구한다.Aij 는 i와 j가 같은 팀일 때의 능력치이며, Aij와 Aji는 값이 다를 수 있으므로 둘 다 더해야 한다.스타트 팀은 c[i] == true AND c[j] == true 이며, 링크 팀은 c[i] == false AND c[j] == false 이다. C++ 소스코드 #include #include..

    BOJ 1748 · 수 이어 쓰기 1

    알고리즘 분류 : 구현 입력으로 N이 주어질 때, 1부터 N까지 수를 이어 붙여서 나온 수의 길이를 구하는 문제다. 자릿수로 나눠서 생각하면 구현이 쉽다.N이 주어졌을 때, 1의 자리가 있는 수는 1부터 N까지이다. 따라서 1의 자리가 있는 수는 (N-1+1)이다.10의 자리가 있는 수는 10부터 N까지이다. 이를 구하면, (N-10+1) 이다.100의 자리가 있는 수는 100부터 N까지이다. 이를 구하면, (N-100+1) 이다.위의 과정을 N의 자릿수 만큼 반복한다. C++ 소스코드 #include int main() { int n; scanf("%d", &n); int ans = 0, i = 1; while (i

    BOJ 13913 · 숨바꼭질 4

    알고리즘 분류 : BFS N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697번 '숨바꼭질' 문제를 변형한 문제다. 최소 시간과 이동한 방법을 출력해야 한다. 이동한 방법은 이동 경로를 역순으로 추적하면 된다. 최소 시간은 이전 문제를 참고.이동 경로를 저장할 path 배열을 만든다.path[다음 좌표] = (현재 좌표) 방식으로 path 배열을 저장한다.K에 도착하면, path 배열을 K부터 시작해서 N까지 역순으로 출력한다. C++ 소스코드 #include #include #include using namespace std; const int MAX = 1e6; int n, k; int dist[MAX+1], path[MAX+1]; void bfs() { queue q; q..

    BOJ 13549 · 숨바꼭질 3

    알고리즘 분류 : BFS N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697 '숨바꼭질' 문제를 변형한 문제다. 최소 시간을 구해야 하는데, 이동 시간에 차이가 있다. 순간 이동(2*X)은 0초 걸리고, X+1, X-1 이동은 1초 걸린다. 0초와 1초 케이스로 나뉘므로, 덱(deque)을 이용하면 좋다.순간 이동(2*X)이 더 빠른 시간(0초)으로 이동할 수 있으므로, X+1, X-1 이동보다 우선순위를 가진다. 순간 이동을 할 경우, 다음 이동 좌표를 덱의 뒤에 넣는다.X+1, X-1 이동을 할 경우, 다음 이동 좌표를 덱의 앞에 넣는다.이동 좌표를 덱에서 꺼낼 때, 덱의 뒤에서부터 pop하면 순간 이동을 먼저 처리할 수 있다. C++ 소스코드 #include #inclu..

    BOJ 12851 · 숨바꼭질 2

    알고리즘 분류 : BFS N부터 K까지 이동하기 위해 걸리는 최소 시간을 구하는 문제다. BOJ 1697번 '숨바꼭질'에서 변형된 문제다. 최소 시간과 그 경우의 수를 구해야 한다. 최소 시간은 이전 문제를 참고한다.x에서 nx에 도착하는 경우의 수는 여러 가지 일 수 있으므로, dist[x]에 아직 방문하지 않은 상태(dist[x]==0)이거나, 이미 방문했더라도 이동 거리가 같다면(dist[nx] == dist[x]+1) 큐에 다음 좌표를 집어넣는다.경우의 수는 k에 도착할 때마다 카운트를 1 증가시킨다. C++ 소스코드 #include #include using namespace std; const int MAX = 1e6; int n, k; int dist[MAX+1]; void bfs() { q..

    BOJ 14226 · 이모티콘

    알고리즘 분류 : BFS S개의 이모티콘을 화면에 만드는 데 걸리는 최소 시간을 구하는 문제다. 3개의 동작이 있고, 각 동작은 1초가 걸리며, 이 동작의 최소 횟수를 구하는 문제이므로, BFS 풀이로 접근할 수 있다. 방문(상태) 체크를 하기 위해서, 2차원 배열이 필요하다.2차원 배열의 인덱스는 [화면에 있는 이모티콘] [클립보드에 있는 이모티콘] 이다.화면에 있는 이모티콘을 x, 클립보드에 있는 이모티콘을 y라 했을 때, 현재 상태를 (x, y)라 하자.다음 상태는 다음과 같다.1. 복사 (x, x)2. 붙여넣기 (x+y, y)3. 삭제 (x-1, y)위 3가지를 기준으로 BFS를 돌려서 최소 시간을 구하면 된다. C++ 소스코드 #include #include using namespace std;..

    BOJ 15666 · N과 M (12)

    알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (8) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. N과 M (11) 문제에서 for문의 시작 지점만 바꾸면 된다. C++ 소스코드 #include #include #include using namespace std; int n, m; vector a, v; void solve(int cnt, int idx) { if (cnt == m) { for (auto k : v) printf("%d ", k); printf("\n"); return; } for (int i=idx; i

    BOJ 15665 · N과 M (11)

    알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (7) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. 중복된 수를 제거하고 (7) 문제와 비슷하게 그대로 돌리면 된다. C++ 소스코드 #include #include #include using namespace std; int n, m; vector a, v; void solve(int cnt) { if (cnt == m) { for (auto k : v) printf("%d ", k); printf("\n"); return; } for (int i=0; i