Study hard

www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net [풀이] 투포인터로 풀 수 있는 문제였다. 투포인터는 하나의 배열에 두 개의 포인터를 사용하는 알고리즘으로, 배열의 원소가 모두 자연수이므로 사용할 수 있었다. 1. start와 end포인터를 0으로 초기화 2. 합이 M보다 작으면 end포인터를 이동시켜 값을 크게 해주기 3. M보다 크면 start포인터를 이동시켜 값을 작게 해주기 4. M과 같으면 count + 1,..

www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net [풀이] 문제에 적힌 조건들을 구현하는 문제였다. 빨간색 보드와 초록색, 파란색 보드를 모두 한 배열로 구현하지 않고, 6*4초록색보드 배열과 4*6파란색보드 배열을 따로 만들어 사용했다. 블록을 놓은 위치를 받아 먼저 초록색 보드와 파란색 보드에 블록을 옮겨줬다. 그리고 while문을 두 개 중첩하여 먼저 해이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하도록 하였다. 꽉찬 행이나 열이 ..

www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [풀이] 치킨집 M개 조합을 구하여 각각 집에 대해 가장 작은 치킨거리를 더하는 문제였다. 처음에 치킨집 M개 위치를 dfs조합으로 구하고, bfs로 각 집에서 시작하여 가장 가까운 치킨집을 구하려고 했는데 시간초과가 나왔다.. 알고보니 각각 집에 대해서 M개의 치킨집까지의 치킨거리를 모두 구하여 가장 작은 수를 더해주면 되는 거였다..! #include #include #include #..

www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net [풀이] 처음 문제를 봤을 때 참 난감한 문제였다.. 시뮬레이션 구현 문제는 규칙이 있기 마련이기에 손으로 그려보면서 규칙을 찾았다. 먼저 각 방향이 다음세대를 그릴 때 어떻게 바뀌는지 찾았다. 방향은 아래와 같이 바뀐다. 0 → 1 (→ ↑) 1 → 2 (↑ ←) 2 → 3 (← ↓) 3 → 0 (↓ →) 그리고 다음세대에 새로 그려지는 드래곤 커브가 어떤 순서로 그려지는 지 찾았다..

www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net [풀이] 문제에 나온 톱니바퀴의 회전 규칙을 구현하는 문제였다. w[n][i]에 n번 톱니바퀴의 i번째 칸의 극을 저장하였다. 그리고 K번 톱니바퀴 번호와 방향을 받을때마다 톱니바퀴들을 회전시켰다. 2번 톱니바퀴를 회전시킨다고 할 때 w[2][6]과 w[1][2]가 같으면 1번 톱니바퀴도 같이 반대방향으로 회전해야한다. 그리고 w[2][2]와 w[3][6]이 같으면 3번 톱니바퀴도 회전해야한다. →재귀함수로..

www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 문제에 있는 조건대로 구현하는 문제였다. bfs를 응용하여 풀었다. 경사로 조건 1. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다. →지금까지 거쳐온 칸 수 저장, 칸 수 ≥ L이면 놓을 수 있다. →낮아지는 경우에는 y + L번째 칸까지 같은 높이인지 확인 2. 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다. →(Map[x][ny] == Map[x][y]+1)인 경우와 (Map[x][..