boj, 백준) 19235. 모노미노도미노 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 2. 문제 개요 가로 칸, 세로 칸이 있다. 블록이 생성되고 블록을 이동시킨다. 4줄이 가득 차면 지우고 블록을 다시 내리고... 등등 색깔이 연한 칸에 블록이 있으면 밑에서부터 지우고.. 등등의 작업을 한다. 점수와 남은 블록의 개수를 출력하는 프로그램을 만들자. 3. 문제 힌트 하나 하나의 동작을 모듈화 시키자. 특별한 알고리즘은 필요 없다. 침착하게 블록들을 어떻게 표현할 수 있을까..
boj, 백준) 19238. 스타트택시 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 2. 문제 개요 N*N의 맵이 있다. M명의 손님이 있고 각 손님은 시작점과 가고 싶은 점(도착점)이 있다. 택시는 매번 손님을 택시로부터 가장 가까운 손님을 태운다. 그리고 그 손님의 목적지까지 데려다준다. 태우고 데려다줄때마다 연료를 소모하는데 연료가 바닥이 나면 -1을 출력. 맵에 있는 모든 손님을 다 태워주고 나면 남은 연료를 출력. 3. 문제 힌트..
백준, boj) 1103. 게임 ( C/ C++)
1. 문제 링크 www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 2. 문제 개요 동전을 움직일 건데, i) 동전이 있는 곳에 쓰여 있는 숫자 X를 본다. ii) 위, 아래, 왼쪽, 오른쪽 방향 중에 한 가지를 고른다 iii) 동전을 위에서 고른 방향으로 X만큼 움직인다, 이때, 중간에 있는 구멍은 무시한다. 3. 문제 힌트 정답률이 상당히 낮다. 나도 문제 풀 때 고려하는 거 다 고려했다고 생각했는데 틀려버린.. 고려해야 하는 것부터 적어본다면, 일단, 보기..
boj, 백준) 13023. ABCDE ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 문제 개요 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 관계가 존재하는지 안 하는지 구하는 프로그램을 작성하시오. 오랜만에 DFS문제를 풀었는데 처음 생각을 잘못해서 10%쯤에서 계속 틀렸다.. 끙끙 앓다가 풀고 나니 허탈한 문제. 3. 문제 힌트 결국 문제의 의미는 4번 연속으로 연결되는, DFS를 할 때 깊이가 4인 것이 단 한 개라도 있으면 1을 출력하면 된다. 위의 가..
boj, 백준) 9426. 중앙값 찾기 ( C++ )
1. 문제 링크 www.acmicpc.net/problem/9426 9426번: 중앙값 측정 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N) 둘째 줄부터 N개 줄에 측정한 온도가 순서대로 주어진다. 온도는 0보다 크거나 같고, 65535보다 작거나 같은 정수이다. www.acmicpc.net 2. 문제 개요 주어진 데이터의 부분 수열의 중앙값을 찾아 모두 합을 구하는 프로그램을 만드시오. 3. 문제 힌트 세그먼트 트리를 사용해보자. 매번 정렬하여 중간값을 꺼내는 방식이나, merge sort처럼 각 세그먼트 트리에 정렬된 값을 갖고 올라가는 것은 O(NK)로 시간이 아슬아슬할 것 같다. 뭔가,, 공간 복잡도를 희생해서 시간 복잡도를 줄일 수 있는 방..
boj, 백준) 2336. 굉장한 학생( C++)
1. 문제 링크 https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 2. 문제 개요 어떤 학생 x보다 시험 3개의 성적이 높은 학생 y가 있다면, 학생 y는 x보다 대단하다고 한다. 어떤 학생 y보다 대단한 학생이 없으면 학생 y는 굉장하다고 한다. 굉장한 학생의 수를 구하는 프로그램을 작성하시오. 3. 문제 풀이 문제 힌트 없이 바로 풀이로 넘어가겠다. 이 부분은 다른 블로그에도 풀이가 많다. 하지만 모두 똑같이 생각하듯이, 글로 설명되어있어서 이해가 잘..