[BOJ 20058] 마법사 상어와 파이어스톰
·
Coding Test/Problem Solving
20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다!! 크게 3가지를 구현해야 한다. 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 모든 칸을 순회하며 인접한 4칸 중 3칸 이상 얼음이 있지 않은 칸은 얼음의 양을 1 줄인다. 남아있는 얼음의 합과 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구한다. 부분 격자 회전 이 부분은 혼자 떠올리기 어려워 다른 사람의 풀이를 참고하였다. 부분 격자이므로 회전시킬 배열의 시작 좌표가 ..
[BOJ 20056] 마법사 상어와 파이어볼
·
Coding Test/Problem Solving
20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 틀렸습니다 삼성 코테의 경우 최대 입력값이 매우 크지 않은 않을 때가 많아 문제에 나온 조건을 충실히 구현하면 된다. 명령 K번만큼 반복문을 수행하며 아래 작업을 진행하면 된다. 처음에는 2.3.1번과 2.3.2번에 적힌 기호가 무슨 뜻인지 몰랐는데 가우스 기호(= x보다 크지 않은 최대 정수)라는 것을 나중에 알았다 ...! 1번을 구현하면서 주황색 박스 친 내용을 주의하여야 한다..
[BOJ 14889] 스타트와 링크
·
Coding Test/Problem Solving
14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다!! 조합을 활용하여 문제를 풀었다. 문제를 푼 자세한 로직은 아래와 같다. 1. 조합을 사용해서 N/2개의 수를 고른다. 해당 수를 start 팀에 배정한다. 2. 반복문으로 N/2개의 수를 고른 경우의 수마다 3번부터 6번 과정을 수행한다. 3. 0 ~ N-1 중 start 팀에 배정되지 않은 수는 link 팀에 배정한다. 4. 조합을 사용해서 0 ~ N/2 중 2개의 수(i, j)를 고른다. 해당 수는 인덱스를 의미하게 된다. ..
[BOJ 14500] 테트로미노
·
Coding Test/Problem Solving
14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 시간초과 한 좌표를 기준으로 테트로미노를 종이 위에 하나 놓는 모든 경우의 수는 해당 좌표를 기준으로 3칸 이동하는 모든 경우의 수와 동일하다. 그러므로 이중 반복문을 사용하여 모든 좌표에 대해 DFS+백트래킹으로 3칸을 이동했을 때 수들의 합을 구한 뒤 최댓값을 구하면 된다. 하지만 여기까지만 구현한다면 예제 입력 3에서 틀릴 것이다. 왜냐하면 T 모양 테트로미노는 3칸 이동하는 것으로 구현하는 것이 불가능하기 때문이다..
[BOJ 14888] 연산자 끼워넣기
·
Coding Test/Problem Solving
1. 문제 설명 2. 구현 아이디어 1 - 틀렸습니다 가장 먼저 생각난 풀이는 순열로 가능한 식을 모두 구한 후, 최댓값과 최솟값을 갱신하는 것이였다. 연산자는 최대 N-1(=10)개가 있고, 10! = 3628800이므로 시간 제한도 넉넉하다. 코드 로직은 아래와 같다. 1. next_permutation으로 순열을 구한다 2. 순열로 구한 연산자 순서에 따라 식의 결과를 갱신한다 - ret = v[0] - 반복문을 돌면서 ... ret = ret (연산자) v[i+1] 3. ret과 mx, mn(최댓값과 최솟값을 담는 변수)를 비교하여 최댓값과 최솟값을 갱신한다 #include using namespace std; #define INF 987654321 int calculate(int a, int b..
[BOJ 16236] 아기 상어
·
Coding Test/Problem Solving
1. 문제 설명 조건: 더 이상 먹을 수 있는 물고기가 공간에 없다면 엄마 상어에게 도움을 요청한다 요구사항: 몇 초동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는가? 이 두 문장을 합하면 더 이상 먹을 수 있는 물고기가 없을 때까지 걸리는 시간을 구해야 한다는 것을 알 수 있다. 물고기를 먹는 조건을 다시 정리하면 아래와 같다. 물고기의 크기가 아기 상어의 크기보다 작아야 한다. 거리가 가까운 순 > X 좌표가 작은 순 > Y 좌표가 작은 순 X = 행, Y = 열 2. 구현 아이디어 1 - 틀렸습니다 이번 문제는 BFS + 빡구현 유형이다. 주어진 조건이 다소 많은데, 해당 조건들을 충족하도록 차근차근 꼼꼼하게 구현하면 풀 수 있다. 아기 상어와 관련된 변수는 걸린 시간, 상어의 ..
짱정연
'분류 전체보기' 카테고리의 글 목록 (5 Page)