구현

문제 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 구현, 시뮬레이션 vector(sharks)에 상어를 입력받는다. 보드 배열(board)의 각 칸에는 현재 위치한 상어의 index가 입력된다. 상어가 위치해 있지 않은 경우 -1이 기본값으로 설정된다. 다음 보드(next_board)의 상태를 나타내는 배열을 만든다. 마찬가지로 기본값은 -1로 설정된다. 다음의 작업이 C번 실행된다. 낚시왕이 위치한 열에 있는 상어 중에서 행이 0과 가장 가까운 상어를 잡는다. 남아 있는 상어의 위..

문제 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 구현, 시뮬레이션 풀이 1 현재 칸에서 왼쪽에 위치한 블록들 중 최고 높이와 오른쪽에 위치한 블록들 중 최고 높이를 구한다. 현재 칸에서는 최고 높이들 중에서 작은 값과 현재 높이의 차만큼의 물이 찬다. 풀이 2 한 행에서 물이 차는 칸을 계산한다. 현재 행에서 블록과 블록으로 막히는 칸들은 물이 차는 칸이다. 행에서 0번 열부터 시작하여 W - 1번 열까지 탐색한다. 처음 블록이 등장했다면 flag를 true로 설정한다. flag가 ..

문제 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 구현, 시뮬레이션 성별에 따라서 스위치를 바꾸는 방법이 다르다. 남자의 경우 입력되는 숫자의 배수에 해당하는 스위치를 바꾼다. // num의 배수에 해당하는 스위치는 상태를 바꾼다. for (int i = num; i > N; for (int i = 1; i > button[i]; } int K; cin >> K; while (K--) { int gender, num; cin >> gender >> num; if (gender == 1) { //..

문제 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 구현, 시뮬레이션 각 칸을 하나의 구조체로 만들었다. 구조체에는 영양분과 나무를 가지는 vector로 구성된다. 처음에는 sort 작업을 없애기 위해, 우선순위 큐로 만들었지만 오히려 시간초과가 발생하였다. struct space { int nutrient = 5; vector trees; }; 계절 별로 함수로 만들어서 해결한다. 봄, 여름에는 (i, j)위치의 칸의 나무를 오름차순으로 정렬하고, 성장 가능한 나무는 따로 vector에..

문제 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 판의 가장자리 부터 bfs를 실시하여 치즈가 있는 칸을 0으로 설정하여 치즈가 모두 녹을 때까지 진행하면 된다. 칸의 가장자리는 에는 치즈가 놓여있지 않기 때문에, (0, 0)에서 bfs를 시작해도 무방하다. 루프를 돌면서 만나는 치즈를 바로 0으로 만들면 해당 칸이 현재 루프에 영향을 미치므로 다음 루프에서의 판을 나타내는 next_board배열을 만들어서 next_board에 해당 칸을 0으로 설정한다. // 다음 칸이 ..

문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 구현, 시뮬레이션, 백트래킹 입력된 cctv에서 가능한 모든 상태를 백트래킹으로 탐색하여 해결하였다. cctv 데이터를 다음의 구조체로 vector에 넣어주었다. struct cctv { int x; int y; bool dir[4] = { false, }; }; cctv를 회전할 때는 dir배열을 회전한 만큼 이동하여 구현하였다. for (int dir = 0; dir < 4; ++dir) { bool temp_dir[4] = { false..

문제 10810번: 공 넣기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 www.acmicpc.net 풀이 구현, 시뮬레이션 단순한 구현 문제로, 배열의 i부터 j까지 k의 값을 넣는 작업을 M번 반복한다. 특정 구간에 동일한 값을 넣을 때, std::fill 함수를 사용했다. std::fill(시작 주소, 끝 주소, 값); std::fill(v.begin() + i, v.begin() + j, k); vector에서도 사용가능하다. 코드 #include #include using namespace std; int nums[102] = { 0, }; int..

문제 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 풀이 구현, 브루트포스 알고리즘 1부터 10000까지의 수, n이 셀프 넘버인지 검사한다. 1부터 n 사이의 수 i에 대해서 (n - i)가 n의 생성자인지 검사한다. (n - i)의 각 자리수의 합을 구한다. (n - i) + ((n - i)의 각 자기수의 합) == n 이라면 (n - i)는 n의 생성자이므로 셀프 넘버가 아니다. 위의 방법으로 셀프 넘버를 찾는다. 코드 #include using nam..

문제

문제 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 구현, 시뮬레이션 현재 order에서 움직일 기어들을 찾아서 방향에 맞게 회전시켜야 한다. 현재 order 기어의 오른쪽 기어들과 왼쪽 기어들을 나눠서 생각한다. // 현재 기어의 오른쪽 기어들 탐색 for (int current_gear = order_gear + 1; current_gear < 4; ++current_gear) { // 현재 기어와 현재 기어 바로 왼쪽 기어의 상태를 비교 if (gear[current_gear - 1][2] !=..