목록전체 글 (217)
Study hard
www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net [풀이] 문제에 나온 규칙대로 구현하는 문제였다. 처음에 모든 상어를 각각의 s만큼 움직이게 해서 위치를 갱신해주었는데, 시간초과가 났다. 최악의 경우 10^3(상어 속력)*10^4(상어의 수)*10^2(C의 크기) = 10^9번의 연산을 하게 되므로 시간초과가 나게 된다! 상어가 위 아래로 움직일 땐 (R-1)*2, 좌우로 움직일 땐 (C-1)*2번 움직이면 같은 자리에 같은 방향을 가지고..
www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net [풀이] dfs 조합 구하는 방법을 이용하여 풀어야하는 문제였다. 먼저 사다리는 Ladder[11][11][31]로 표현하였다. Ladder[b][b+1][a] = true는 b번 세로선과 b+1번 세로선이 a번째줄의 가로선에 의해 연결되었다는 뜻이다. dfs로 추가할 가로선을 선정하고 0번 이상 추가했으면(3번 이하로) i번 세로선의 결과가 i번이 나오는지 확인하고 최솟값을 갱신한다. ※착각해서 조합을 구하..
www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net [풀이] 간단한 수학문제였다. 총감독관은 시험장 수만큼 있으므로 각 시험장에서 B만큼씩 빼고 부감독관의 최소 수를 구하면 된다. ※답이 int범위를 초과할 수 있으므로 long long자료형을 사용해야한다. #include using namespace std; const int Max = 1000000; int N; long long A[Max]; lon..
www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net [풀이] dfs 중복순열을 구하는 방법을 이용하여 5번 이동시키는 모든 경우에 대해 얻을 수 있는 가장 큰 블록을 구하였다. #include #include using namespace std; int N; int Board[20][20]; int c_Board[20][20]; int Order[5]; const int dx[] = { -1,1,0,0 };//위,아래 const in..
www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [풀이] dfs를 사용하여 각각 방향마다 어떤 상태가 되는지 확인하는 방법으로 풀었다. dfs를 10번 호출했으면 return해주었다. 빨간 구슬을 먼저 움직여주고, 파란 구슬을 움직여서 파란 구슬이 구멍에 빠졌으면 return, 빨간 구슬만 구멍에 빠졌으면 최소값을 갱신해주었다. #include #include //min #include using namesp..
www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [풀이] 문제에서 주어진 규칙대로 구현하는 문제였다. 구현 순서 1. 봄 -나무가 자기 나이만큼 양분 먹고 나이+1 -양분 부족하면 즉시 죽음 2. 여름 -죽은 나무 → 양분 (죽은 나무의 나이/2) 3. 가을 -나무 나이가 5배수면 8개 방향으로 번식 4. 겨울 -각 칸에 A[r][c]만큼 양분 추가 배열 Map[11][11] 사용하여 각 칸에 남은 양분 양을 저장하였다. deque자료구조를 ..