삼성 SW 역량 테스트 기출 문제 + 삼성 A형 기출 문제
카테고리: Algorithm
Chapter 01 시뮬레이션
01-1 뱀 ( 3190 )
- 첫째 줄에 게임이 몇 초에 끝나는지 출력한다
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
int board_size; // 게임판의 크기
int num_of_apple; // 먹이의 개수
int num_of_order; // 뱀의 이동 방향 변경 횟수
deque<pair<int, int>> snake_body; // 뱀의 몸통 좌표
vector<int> order_time; // 뱀의 이동 방향 변경 시간
vector<char> order_direction; // 뱀의 이동 방향 변경 방향
int game_board[100][100]; // 게임판 상태
int dx[] = { 1, 0, -1, 0 }; // x좌표 이동 방향
int dy[] = { 0, 1, 0, -1 }; // y좌표 이동 방향
// 뱀 게임 실행 함수
int run_game(int start_x, int start_y)
{
int direction = 0; // 초기 방향은 오른쪽
int cnt = 0; // 게임 진행 시간
int x, y; // 뱀 머리 좌표
int order_idx = 0; // 뱀의 이동 방향 변경 명령 인덱스
snake_body.push_front(make_pair(start_x, start_y)); // 뱀 머리 좌표 큐에 추가
game_board[start_y][start_x] = 2; // 뱀이 있는 위치 표시
while (1)
{
x = snake_body.front().first;
y = snake_body.front().second;
cnt++;
int next_x = x + dx[direction];
int next_y = y + dy[direction];
// 게임 종료 조건
if (next_x < 0 || next_y < 0 || board_size <= next_x || board_size <= next_y || game_board[next_y][next_x] == 2)
return cnt;
snake_body.push_front(make_pair(next_x, next_y)); // 뱀 머리를 다음 위치로 이동
// 먹이를 먹지 않은 경우
if (game_board[next_y][next_x] != 1)
{
int tail_x = snake_body.back().first;
int tail_y = snake_body.back().second;
game_board[tail_y][tail_x] = 0; // 꼬리 제거
snake_body.pop_back(); // 뱀 꼬리 제거
}
game_board[next_y][next_x] = 2; // 뱀이 있는 위치 표시
// 뱀의 이동 방향 변경
if (cnt == order_time[order_idx])
{
if (order_direction[order_idx] == 'L')
{ // 왼쪽으로 회전
direction += 3;
direction %= 4;
}
else
{ // 오른쪽으로 회전
direction += 1;
direction %= 4;
}
if (order_idx < order_time.size() - 1)
{
order_idx++;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> board_size;
// 사과
cin >> num_of_apple;
for (int i = 0; i < num_of_apple; i++)
{
int applex, appley;
cin >> applex >> appley;
game_board[applex - 1][appley - 1] = 1;
}
// 명령
cin >> num_of_order;
for (int i = 0; i < num_of_order; i++)
{
int t;
char d;
cin >> t >> d;
order_time.push_back(t);
order_direction.push_back(d);
}
cout << run_game(0, 0);
return 0;
}
01-2 주사위 굴리기 ( 14499 )
- 이동할 때마다 주사위의 윗 면에 쓰여 있는 수를 출력한다 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안 된다
// https://excited-hyun.tistory.com/215 참고
#include<bits/stdc++.h>
using namespace std;
int mymap[20][20];
int X[5] = { 0, 1, -1, 0, 0 };
int Y[5] = { 0, 0, 0, -1, 1 };
vector<int> dice(6, 0);
int main()
{
int n, m, x, y, k;
scanf("%d %d %d %d %d", &n, &m, &y, &x, &k);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
scanf("%d", &mymap[i][j]);
}
int move;
for (int i = 0; i < k; ++i)
{
scanf("%d", &move);
int newX = x + X[move];
int newY = y + Y[move];
if (newX < 0 || newY < 0 || m <= newX || n <= newY)
continue;
if (move == 1)
dice = { dice[3], dice[1], dice[0], dice[5], dice[4], dice[2] };
else if (move == 2)
dice = { dice[2], dice[1], dice[5], dice[0], dice[4], dice[3] };
else if (move == 3)
dice = { dice[4], dice[0], dice[2], dice[3], dice[5], dice[1] };
else if (move == 4)
dice = { dice[1], dice[5], dice[2], dice[3], dice[0], dice[4] };
if (mymap[newY][newX] == 0)
mymap[newY][newX] = dice[5];
else
{
dice[5] = mymap[newY][newX];
mymap[newY][newX] = 0;
}
cout << dice[0] << endl;
x = newX;
y = newY;
}
return 0;
}
01-3 로봇 청소기 ( 14503 )
- 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오
// https://blog.naver.com/PostView.naver?blogId=fbfbf1&logNo=222472445249&categoryNo=34&parentCategoryNo=37&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView 참고
#include<bits/stdc++.h>
using namespace std;
int board[52][52];
bool check[52][52];
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int sum = 0;
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int N, M, r, c, d;
cin >> N >> M >> r >> c >> d;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
cin >> board[i][j];
}
}
while (true)
{
if (check[r][c] == false)
{
check[r][c] = true;
sum++;
}
bool ch = false;
for (int i = 0; i < 4; ++i)
{
d = (d + 3) % 4;
int nx = c + dx[d];
int ny = r + dy[d];
if (nx < 0 || ny < 0 || M <= nx || N <= ny) continue;
if (board[ny][nx] == 0 && check[ny][nx] == false)
{
c = nx;
r = ny;
ch = true;
break;
}
}
if (!ch)
{
int back = (d + 2) % 4;
int nx = c + dx[back];
int ny = r + dy[back];
if (nx < 0 || ny < 0 || M <= nx || N <= ny) break;
if (board[ny][nx] == 1) break;
c = nx;
r = ny;
}
}
cout << sum << "\n";
}
01-4 톱니바퀴 (2) ( 15662 )
- 톱니바퀴 T개의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오
// https://intaehwang.tistory.com/108 참고
#include<bits/stdc++.h>
using namespace std;
int gear[1001][8];
int check[1001];
int main()
{
int t;
cin >> t;
for (int i = 1; i <= t; i++)
{
for (int j = 0; j < 8; j++)
scanf("%1d", &gear[i][j]);
}
int k;
cin >> k;
for (int i = 0; i < k; i++)
{
memset(check, 0, sizeof(check));
int x, y;
cin >> x >> y;
check[x] = y;
for (int j = x; j < t; j++)
{
if (gear[j][2] != gear[j+1][6]) check[j+1] = -check[j];
else break;
}
for (int j = x; 1 < j; j--)
{
if (gear[j-1][2] != gear[j][6]) check[j-1] = -check[j];
else break;
}
for (int j = 1; j <= t; j++)
{
if (check[j] == 0) continue;
else if (check[j] == 1)
{
int tmp = gear[j][7];
for(int cur = 7; 0 < cur; --cur) gear[j][cur] = gear[j][cur-1];
gear[j][0] = tmp;
}
else if (check[j] == -1)
{
int tmp = gear[j][0];
for(int cur = 0; cur < 7; ++cur) gear[j][cur] = gear[j][cur+1];
gear[j][7] = tmp;
}
}
}
int ans = 0;
for (int i = 1; i <= t; i++)
if (gear[i][0] == 1) ans += 1;
cout << ans << endl;
}
01-5 드래곤 커브 ( 15685 )
- 크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오
// https://velog.io/@sj-lee33/%EB%B0%B1%EC%A4%80-15685-%EB%93%9C%EB%9E%98%EA%B3%A4-%EC%BB%A4%EB%B8%8C-c-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%92%80%EC%9D%B4 참고
#include<bits/stdc++.h>
using namespace std;
#define MAX 101
int N;
int x, y, d, g, cnt;
int mymap[MAX][MAX];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
vector<int> direction;
void Make_Dragon_Curve()
{
int size = direction.size();
for (int i = size - 1; 0 <= i; i--)
{
int temp = (direction[i] + 1) % 4;
x += dx[temp];
y += dy[temp];
mymap[y][x] = 1;
direction.push_back(temp);
}
}
void Count_Square()
{
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
if (mymap[i][j] == 1 && mymap[i][j + 1] == 1 && mymap[i + 1][j + 1] && mymap[i + 1][j] == 1)
cnt++;
}
}
}
void Solution()
{
cin >> N;
while (N--)
{
direction.clear();
cin >> x >> y >> d >> g;
// initialize
mymap[y][x] = 1;
// generation 0
x += dx[d];
y += dy[d];
mymap[y][x] = 1;
direction.push_back(d);
// next 'g' generations
while (g--)
{
Make_Dragon_Curve();
}
}
Count_Square();
cout << cnt << endl;
}
int main()
{
Solution();
}
01-6 인구 이동 ( 16234 )
- 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오
#include<bits/stdc++.h>
using namespace std;
int arr[55][55];
bool visited[55][55];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n, l, r, uni, sum;
queue<pair<int, int>> que;
// y, x 좌표를 시작으로 DFS 탐색을 하면서 인구 이동이 가능한 국가들을 모두 찾아줌
void dfs(int y, int x)
{
// 시작 좌표를 큐에 추가하고 방문 체크를 함
que.push({ y, x });
visited[y][x] = true;
sum = sum + arr[y][x];
uni++;
// 현재 위치에서 4방향으로 이동하면서 인구 이동이 가능한 국가들을 찾음
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i], nx = x + dx[i];
if (nx < 0 || ny < 0 || n <= nx || n <= ny || visited[ny][nx]) continue;
if (abs(arr[y][x] - arr[ny][nx]) <= r && l <= abs(arr[y][x] - arr[ny][nx]))
dfs(ny, nx);
}
}
int main()
{
scanf("%d %d %d", &n, &l, &r);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) scanf("%d", &arr[i][j]);
int ret = 0; bool move = false;
do
{
move = false;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// 아직 방문하지 않은 국가를 시작으로 DFS 탐색을 시작함
uni = 0;
if (!visited[i][j])
{
sum = 0;
dfs(i, j);
// 큐에 저장된 모든 국가들의 인구수를 현재 연합의 인구수 평균값으로 업데이트함
while (!que.empty())
{
auto pos = que.front();
que.pop();
arr[pos.first][pos.second] = sum / uni;
}
// 인구 이동이 발생한 경우 move를 true로 세팅
if (sum != arr[i][j]) move = true;
}
}
}
// 인구 이동이 발생한 경우 날짜를 증가시킨다
if (move) ret++;
} while (move);
printf("%d", ret);
}
// 이 코드는 도대체 어떻게 돌아가는지 연구가 필요하다
// for (int i = 0; i < 4; i++) 여기 부분에서
// sum = arr[ny][nx] + dfs(ny, nx); 이 코드가 말이 안된다
#include<bits/stdc++.h>
using namespace std;
int arr[55][55];
bool visited[55][55];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n, l, r, uni, sum;
queue<pair<int, int>> que;
// y, x 좌표를 시작으로 DFS 탐색을 하면서 인구 이동이 가능한 국가들을 모두 찾아줌
int dfs(int y, int x)
{
// 시작 좌표를 스택에 추가하고 방문 체크를 함
que.push({ y, x });
visited[y][x] = true;
uni++;
// 현재 위치에서 4방향으로 이동하면서 인구 이동이 가능한 국가들을 찾음
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i], nx = x + dx[i];
if (nx < 0 || ny < 0 || n <= nx || n <= ny || visited[ny][nx]) continue;
if (abs(arr[y][x] - arr[ny][nx]) <= r && l <= abs(arr[y][x] - arr[ny][nx])) sum = arr[ny][nx] + dfs(ny, nx);
}
return sum;
}
int main()
{
scanf("%d %d %d", &n, &l, &r);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) scanf("%d", &arr[i][j]);
int ret = 0; bool move = false;
do
{
move = false;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// 아직 방문하지 않은 국가를 시작으로 DFS 탐색을 시작함
uni = 0;
if (!visited[i][j])
{
sum = 0;
sum = arr[i][j] + dfs(i, j);
// 큐에 저장된 모든 국가들의 인구수를 현재 연합의 인구수 평균값으로 업데이트함
while (!que.empty())
{
auto pos = que.front();
que.pop();
arr[pos.first][pos.second] = sum / uni;
}
// 인구 이동이 발생한 경우 카운트를 증가시킴
if (sum != arr[i][j]) move = true;
}
}
}
// 인구 이동이 발생한 경우 날짜를 증가시킨다
if (move) ret++;
} while (move);
printf("%d", ret);
}
01-7 미세먼지 안녕! ( 17144 )
- 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다
#include <iostream>
#include <vector>
using namespace std;
int R, C, T;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int board[51][51];
vector<int> cleaner; // 공기청정기 위치
// 미세먼지 확산 함수
void CalDiffusion()
{
vector<vector<int>> temp(51, vector<int>(51, 0)); // 확산될 미세먼지 임시 보관
// 미세먼지 있는 칸 별로 확산되는 미세먼지 양 계산
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (0 < board[i][j]) // 미세먼지 있는 칸
{
int dust = board[i][j] / 5; // 확산되는 미세먼지 양 계산
if (dust == 0) continue; // 예시 그림을 보면 나누기 5를 했을때 1 이상 나오지 않으면 확산되지 않음
int cnt = 0; // 확산된 칸 갯수
for (int dir = 0; dir < 4; dir++) // 사방 탐색
{
int ny = i + dy[dir];
int nx = j + dx[dir];
if (nx < 0 || ny < 0 || C <= nx || R <= ny) continue; // 범위 체크
if (board[ny][nx] == -1) continue; // 공기청정기 체크
temp[ny][nx] = temp[ny][nx] + dust; // 미세먼지 확산
cnt++;
}
// 확산 이후 미세먼지 감소
board[i][j] = board[i][j] - (dust * cnt);
}
}
}
// 확산된 미세먼지와 칸 별로 줄어든 미세먼지 합산
// 확산된 먼지가 다른 칸의 먼지양을 나누는 계산을
// 할때 영향을 끼치면 안되서 이렇게 하는것으로 추정
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
board[i][j] = board[i][j] + temp[i][j];
}
}
}
void CleanDust()
{
// upward
int cr = cleaner[0];
for (int i = cr - 1; 0 < i; i--) board[i][0] = board[i - 1][0];
for (int j = 0; j < C - 1; j++) board[0][j] = board[0][j + 1];
for (int i = 0; i < cr; i++) board[i][C - 1] = board[i + 1][C - 1];
for (int j = C - 1; 1 < j; j--) board[cr][j] = board[cr][j - 1];
board[cr][1] = 0;
// downward
cr = cleaner[1];
for (int i = cr + 1; i < R - 1; i++) board[i][0] = board[i + 1][0];
for (int j = 0; j < C - 1; j++) board[R - 1][j] = board[R - 1][j + 1];
for (int i = R - 1; cr < i; i--) board[i][C - 1] = board[i - 1][C - 1];
for (int j = C - 1; 1 < j; j--) board[cr][j] = board[cr][j - 1];
board[cr][1] = 0;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> R >> C >> T;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cin >> board[i][j];
if (board[i][j] == -1) cleaner.push_back(i);
}
}
while (T--)
{
CalDiffusion();
CleanDust();
}
int answer = 0;
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (board[i][j] > 0) answer += board[i][j];
}
}
cout << answer;
}
01-8 이차원 배열과 연산 ( 17140 )
- A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다
#include<bits/stdc++.h>
using namespace std;
int grid[101][101]; // 101x101 크기의 2차원 배열 선언
int rows, cols, target; // 행, 열, 타겟값
int rowCount = 3; // 현재 행의 개수
int colCount = 3; // 현재 열의 개수
void sortRows() // 각 행에 대해 정렬하는 함수
{
int cnt = 0; // 열 개수를 저장하는 변수
for (int i = 0; i < rowCount; i++) // 모든 행에 대해 반복
{
int freq[101] = { 0 }; // 각 숫자의 등장 횟수를 저장하는 배열
for (int j = 0; j < colCount; j++) // 현재 행의 모든 열에 대해 반복
{
freq[grid[i][j]]++; // 해당 숫자의 등장 횟수 증가
}
vector<pair<int, int>> freqPairs; // 등장 횟수와 해당 숫자를 저장하는 벡터
for (int j = 1; j < 101; j++) // 1부터 100까지 모든 숫자에 대해 반복
{
if (0 < freq[j]) // 해당 숫자가 등장한 경우
{
freqPairs.push_back({ freq[j], j }); // 등장 횟수와 해당 숫자를 벡터에 추가
}
}
sort(freqPairs.begin(), freqPairs.end()); // 등장 횟수를 기준으로 오름차순 정렬
int idx = 0; // 현재 열 인덱스를 저장하는 변수
int size = freqPairs.size(); // 등장한 숫자의 개수
for (int j = 0; j < size; j++) // 등장한 숫자에 대해 반복
{
grid[i][idx] = freqPairs[j].second; // 해당 숫자를 현재 열에 저장
grid[i][idx + 1] = freqPairs[j].first; // 해당 숫자의 등장 횟수를 다음 열에 저장
idx += 2; // 열 인덱스를 2 증가
}
cnt = max(cnt, size * 2); // 열 개수를 갱신
for (int j = idx; j < 101; j++) grid[i][j] = 0; // 남은 열을 0으로 초기화
}
colCount = cnt; // 열 개수를 업데이트
}
void sortCols()
{
// cnt: 현재 가장 긴 열의 길이
int cnt = 0;
for (int i = 0; i < colCount; i++)
{
// freq: 열에서 각 숫자의 등장 횟수를 저장하는 배열
int freq[101] = { 0 };
for (int j = 0; j < rowCount; j++)
{
freq[grid[j][i]]++;
}
// freqPairs: 등장 횟수가 1 이상인 숫자와 그 횟수를 저장하는 벡터
vector<pair<int, int>> freqPairs;
for (int j = 1; j < 101; j++)
{
if (0 < freq[j])
{
freqPairs.push_back({ freq[j], j });
}
}
// 등장 횟수가 적은 숫자부터 정렬
sort(freqPairs.begin(), freqPairs.end());
// idx: 현재 열의 어디까지 값을 넣었는지를 저장하는 인덱스
int idx = 0;
int size = freqPairs.size();
for (int j = 0; j < size; j++)
{
grid[idx][i] = freqPairs[j].second; // 숫자를 넣음
grid[idx + 1][i] = freqPairs[j].first; // 등장 횟수를 넣음
idx += 2;
}
cnt = max(cnt, size * 2); // 현재 가장 긴 열의 길이 업데이트
// 나머지 빈 공간에는 0을 채움
for (int j = idx; j < 101; j++) grid[j][i] = 0;
}
rowCount = cnt; // 새로운 행의 개수를 업데이트
}
int main()
{
int time = 0;
// 입력 받기
cin >> rows >> cols >> target;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> grid[i][j];
}
}
// 목표값이 나올 때까지 정렬을 반복
while (time <= 100)
{
if (grid[rows - 1][cols - 1] == target) break; // 목표값이 나오면 종료
if (colCount <= rowCount) sortRows(); // 행 기준으로 정렬
else sortCols(); // 열 기준으로 정렬
time++;
}
// 목표값을 찾지 못한 경우 -1 출력, 찾은 경우에는 시간 출력
if (100 < time) cout << "-1";
else cout << time;
}
01-9 컨베이어 벨트 위의 로봇 ( 20055 )
- 몇 번째 단계가 진행 중일때 종료되었는지 출력한다
// 이 문제에서 사용된 로직은 DP스러운 문제에서 필요한 경우가 있다
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N, K;
cin >> N >> K;
vector<bool> occupied(2 * N, false);
vector<int> A(2 * N);
for (auto& item : A)
cin >> item;
int counter = 0;
while (true)
{
++counter;
// 1.
rotate(occupied.rbegin(), occupied.rbegin() + 1, occupied.rend());
rotate(A.rbegin(), A.rbegin() + 1, A.rend());
occupied[N - 1] = false;
// 2.
for (int i = N - 1; 0 < i; --i)
{
if (occupied[i - 1] && A[i] && !occupied[i])
{
swap(occupied[i - 1], occupied[i]);
--A[i];
}
}
occupied[N - 1] = false;
// 3.
if (A[0])
{
occupied[0] = true;
--A[0];
}
// 4.
if (K <= count_if(A.begin(), A.end(), [](int item) { return item == 0; }))
{
break;
}
}
cout << counter;
return 0;
}
01-10 마법사 상어와 파이어볼 ( 20056 )
- 마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다
// https://www.youtube.com/watch?v=g2B-rKwaVUQ 14 : 57 참고
#include<bits/stdc++.h>
using namespace std;
int N, M, K;
// 볼을 나타내는 구조체 선언
struct Ball
{
int y, x; // 좌표
int m, s, d; // 질량, 속도, 방향
};
// 각 좌표에 위치한 Ball을 저장할 벡터 배열 선언
vector<Ball> balls;
vector<Ball> mat[53][53];
// 각 방향을 나타내는 배열 선언 ( 12시 방향부터 시계 방향으로 )
int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
void solution()
{
while (K--)
{
// Ball 움직이기
for (int i = 0; i < balls.size(); i++)
{
int y = balls[i].y;
int x = balls[i].x;
int m = balls[i].m;
int s = balls[i].s;
int d = balls[i].d;
// 현재 속력으로 이동한 거리 계산
int move = s % N;
int ny = y + dy[d] * move; // 새로운 y 좌표
int nx = x + dx[d] * move; // 새로운 x 좌표
// 경계를 넘어갈 경우 위치 수정
if (N <= ny) ny = ny - N;
if (N <= nx) nx = nx - N;
if (ny < 0) ny = ny + N;
if (nx < 0) nx = nx + N;
// 새로운 위치에 Ball 추가
mat[ny][nx].push_back({ ny, nx, m, s, d });
}
// 움직임이 완료된 Ball들 합치기
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (2 <= mat[i][j].size())
{
int sum_m = 0, sum_s = 0;
int odd = 0, even = 0;
int size = mat[i][j].size();
// Ball의 속력, 방향, 질량의 합 구하기
for (int t = 0; t < size; t++)
{
sum_m = sum_m + mat[i][j][t].m;
sum_s = sum_s + mat[i][j][t].s;
if (mat[i][j][t].d % 2 == 0) even++;
else odd++;
}
mat[i][j].clear(); // 합쳐진 Ball 제거
// 소멸될 예정인 파이어볼은 미리 거르자
if (sum_m / 5 == 0) continue;
// 방향 결정
if (odd == 0 || even == 0)
{
for (int nd = 0; nd < 7; nd = nd + 2)
{
mat[i][j].push_back({ i, j, sum_m / 5, sum_s / size, nd });
}
}
else
{
for (int nd = 1; nd < 8; nd = nd + 2)
{
mat[i][j].push_back({ i, j, sum_m / 5, sum_s / size, nd });
}
}
}
}
}
// 합치기가 완료된 Ball을 저장하기
balls.clear();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int t = 0; t < mat[i][j].size(); t++)
{
balls.push_back(mat[i][j][t]);
}
mat[i][j].clear();
}
}
}
// 남은 질량의 합 구하기
int ans = 0;
for (int i = 0; i < balls.size(); i++)
ans = ans + balls[i].m;
cout << ans << endl;
}
int main(void)
{
cin >> N >> M >> K;
for (int i = 0; i < M; i++)
{
int y, x, m, s, d;
cin >> y >> x >> m >> s >> d;
balls.push_back({ y, x, m, s, d });
}
solution();
}
// 킵 해두자
// https://kibbomi.tistory.com/193
01-11 상어 초등학교 ( 21608 )
- 첫째 줄에 학생의 만족도의 총 합을 출력한다
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
//위,아래,왼,우 방향 배열
int x_direction[] = { 0,0,-1,1 };
int y_direction[] = { -1,1,0,0 };
int answer = 0;
int n;
// n 입력 받기
cin >> n;
// n x n 크기의 2차원 벡터 seats를 만들고 0으로 초기화
vector<vector<int>> seats(n, vector<int>(n, 0));
// n x n + 1 크기의 2차원 벡터 like와 1차원 벡터 students를 만들기
vector<vector<int>> like(n * n + 1, vector<int>(4, 0));
vector<int> students(n * n + 1);
// 학생들의 좋아하는 학생 번호 입력받기
for (int i = 0; i < n * n; i++)
{
cin >> students[i];
for (int j = 0; j < 4; j++)
cin >> like[students[i]][j];
}
// 배치 시작
for (int s = 0; s < n * n; s++)
{
int student = students[s];
int most_like = -1, most_empty = -1, selected_y = -1, selected_x = -1;
// 각 자리마다 좋아하는 학생과 인접한 빈 자리 수 계산하기
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
// 이미 학생이 있는 자리는 건너뛰기
if (seats[i][j] != 0) continue;
int cur_like = 0, cur_empty = 0;
for (int dir = 0; dir < 4; dir++)
{
int ny = i + y_direction[dir], nx = j + x_direction[dir];
// 범위를 벗어나는 경우 건너뛰기
if (nx < 0 || ny < 0 || n <= nx || n <= ny) continue;
if (seats[ny][nx] == 0)
{
cur_empty++;
continue;
}
// 좋아하는 학생인 경우 인접한 학생 수 1 증가
for (int k = 0; k < 4; k++)
{
if (seats[ny][nx] == like[student][k])
{
cur_like++;
break;
}
}
}
// 조건에 맞는 자리 선택하기
if (most_like < cur_like)
{
most_like = cur_like, most_empty = cur_empty;
selected_y = i, selected_x = j;
}
else if (most_like == cur_like)
{
if (most_empty < cur_empty)
{
most_like = cur_like, most_empty = cur_empty;
selected_y = i, selected_x = j;
}
}
else continue;
}
// 선택된 자리에 학생 배치하기
seats[selected_y][selected_x] = student;
}
// 만족도 계산
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int student = seats[i][j];
int satisfaction = 0;
// 상하좌우 인접한 자리에 좋아하는 학생이 있으면 만족도 증가
for (int dir = 0; dir < 4; dir++)
{
int ny = i + y_direction[dir], nx = j + x_direction[dir];
if (nx < 0 || ny < 0 || n <= nx || n <= ny) continue;
for (int k = 0; k < 4; k++)
{
if (seats[ny][nx] == like[student][k])
{
satisfaction++;
break;
}
}
}
// 만족도가 1 이상이면 answer에 추가
if (satisfaction)
{
int ans = 1;
for (int score = 0; score < satisfaction - 1; score++) ans = ans * 10;
answer = answer + ans;
}
}
cout << answer << endl;
return 0;
}
// https://gusdnr69.tistory.com/296 킵 해두자
01-12 마법사 상어와 비바라기 ( 21610 )
- 첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int main()
{
int gridSize, numMoves;
int answer = 0;
queue<pair<int, int>> cloudQueue;
vector<vector<int>> grid(51, vector<int>(51, 0));
int directionY[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int directionX[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
// 그리드 사이즈와 이동 횟수 입력받기
cin >> gridSize >> numMoves;
// 그리드 초기화
for (int i = 1; i <= gridSize; i++)
for (int j = 1; j <= gridSize; j++)
cin >> grid[i][j];
// 초기 구름 위치 설정
cloudQueue.push(make_pair(gridSize, 1));
cloudQueue.push(make_pair(gridSize, 2));
cloudQueue.push(make_pair(gridSize - 1, 1));
cloudQueue.push(make_pair(gridSize - 1, 2));
// 이동 횟수만큼 반복
while (numMoves--)
{
int moveDirection, moveDistance, queueSize;
vector<vector<bool>> visited(51, vector<bool>(51, false));
vector<pair<int, int>> cloudPositions;
// 이동 방향과 거리 입력받기
cin >> moveDirection >> moveDistance;
// 현재 구름 위치에서 이동 방향과 거리에 따라 이동하기
queueSize = cloudQueue.size();
for (int i = 0; i < queueSize; i++)
{
int y = cloudQueue.front().first;
int x = cloudQueue.front().second;
cloudQueue.pop();
for (int j = 0; j < moveDistance; j++)
{
x += directionX[moveDirection];
y += directionY[moveDirection];
// 그리드를 벗어나는 경우 위치 조정
if (x == 0)
x = gridSize;
else if (gridSize < x)
x = 1;
if (y == 0)
y = gridSize;
else if (gridSize < y)
y = 1;
}
grid[y][x]++;
cloudPositions.push_back(make_pair(y, x));
visited[y][x] = true;
}
// 현재 구름 위치에서 대각선 방향으로 인접한 칸의 물의 양 증가시키기
for (int i = 0; i < cloudPositions.size(); i++)
{
int y = cloudPositions[i].first;
int x = cloudPositions[i].second;
for (int j = 2; j <= 8; j += 2)
{
int nx = x + directionX[j];
int ny = y + directionY[j];
if (1 <= nx && 1 <= ny && nx <= gridSize && ny <= gridSize && 1 <= grid[ny][nx])
grid[y][x]++;
}
}
// 구름을 이동시킨 후 물의 양이 2 이상이 되는 칸에 새로운 구름 생성
for (int i = 1; i <= gridSize; i++)
for (int j = 1; j <= gridSize; j++)
if (2 <= grid[i][j] && !visited[i][j])
{
cloudQueue.push(make_pair(i, j));
grid[i][j] -= 2;
}
}
// 최종적으로 남아있는 물의 양 계산
for (int i = 1; i <= gridSize; i++)
for (int j = 1; j <= gridSize; j++)
if (0 < grid[i][j])
answer += grid[i][j];
// 결과 출력
cout << answer;
return 0;
}
// https://eunchanee.tistory.com/398 킵 해두자
// https://imnotabear.tistory.com/562 // 킵 해두자
Chapter 02 그래프
02-1 파이프 옮기기 1 ( 17070 )
- 첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다 이동시킬 수 없는 경우에는 0을 출력한다 방법의 수는 항상 1,000,000보다 작거나 같다
02-2 게리맨더링 ( 17471 )
- 첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다
Chapter 03 DFS
03-1 문제
- 설명
Chapter 04 백트래킹
04-1 문제
- 설명
Chapter 05 BFS
05-1 연구소 ( 14502 )
- 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다
#include<bits/stdc++.h>
using namespace std;
int answer = 0;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
// 여기서는 참조자를 사용해도 된다
void BFS(vector<vector<int>>& mymap)
{
queue<pair<int, int>> que;
// 바이러스 최초 위치들을 모두 큐에 담는다
for (int y = 0; y < mymap.size(); y++)
{
for (int x = 0; x < mymap[0].size(); x++)
{
if (mymap[y][x] == 2)
que.push({ x, y });
}
}
// 바이러스를 최대한 퍼뜨린다
while (!que.empty())
{
int x = que.front().first;
int y = que.front().second;
que.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || mymap[0].size() <= nx || mymap.size() <= ny || mymap[ny][nx] != 0)
continue;
mymap[ny][nx] = 2;
que.push({ nx, ny });
}
}
// 바이러스가 모두 퍼진 상태에서 안전 영역 크기를 계산한다
int cnt = 0;
for (int y = 0; y < mymap.size(); y++)
{
for (int x = 0; x < mymap[0].size(); x++)
{
if (mymap[y][x] == 0)
cnt++;
}
}
answer = max(answer, cnt);
}
// 여기서는 참조자를 사용하면 안된다
void DFS(vector<vector<int>> mymap, int x, int y, int cnt)
{
mymap[y][x] = 1;
cnt = cnt - 1;
// 벽을 더이상 세울수 없다면 바이러스를 퍼뜨린다
if (cnt == 0)
{
BFS(mymap);
return;
}
// 벽 2개를 세울수 있는 모든 경우의 수를 체크한다
for (int y = 0; y < mymap.size(); y++)
{
for (int x = 0; x < mymap[0].size(); x++)
{
if (mymap[y][x] == 0)
DFS(mymap, x, y, cnt);
}
}
}
int main()
{
int N, M;
cin >> N >> M;
vector<vector<int>> mymap(N, vector<int>(M, 0));
for (int y = 0; y < N; y++)
{
for (int x = 0; x < M; x++)
cin >> mymap[y][x];
}
// 벽 3개를 세울수 있는 모든 경우의 수를 체크한다
for (int y = 0; y < N; y++)
{
for (int x = 0; x < M; x++)
{
if (mymap[y][x] == 0)
DFS(mymap, x, y, 3);
}
}
cout << answer << endl;
return 0;
}
Chapter 06 완전탐색
06-1 테트로미노 ( 14500 )
- 첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다
// https://9967han.tistory.com/15 참고
#include<bits/stdc++.h>
using namespace std;
const int MAX = 501;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int N, M, ans = 0;
void getMaxNum(vector<vector<int>>& mymap, vector<vector<bool>>& visited, int x, int y, int cnt, int curScore)
{
// 블록이 4개라면 스코어 갱신이 가능한지 체크
if (cnt == 4)
{
if (ans < curScore) ans = curScore;
return;
}
// 현재 노드에서 만들수 있는 모든 도형을 만들자
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || M <= nx || N <= ny || visited[ny][nx]) continue;
visited[ny][nx] = true;
getMaxNum(mymap, visited, nx, ny, cnt + 1, curScore + mymap[ny][nx]);
visited[ny][nx] = false;
}
}
int main()
{
vector<vector<int>> mymap(MAX, vector<int>(MAX, 0));
vector<vector<bool>> visited(MAX, vector<bool>(MAX, false));
cin >> N >> M;
for (int y = 0; y < N; ++y)
{
for (int x = 0; x < M; ++x)
{
cin >> mymap[y][x];
}
}
for (int y = 0; y < N; ++y)
{
for (int x = 0; x < M; ++x)
{
// 모든 노드를 방문한다
visited[y][x] = true;
getMaxNum(mymap, visited, x, y, 1, mymap[y][x]);
visited[y][x] = false;
// ㅏ ㅓ ㅗ ㅜ 를 만들자
if (0 <= y - 1 && x + 1 < M && y + 1 < N) //ㅏ
{
ans = max(ans, (mymap[y - 1][x] + mymap[y][x] + mymap[y][x + 1] + mymap[y + 1][x]));
}
if (0 <= y - 1 && 0 <= x - 1 && y + 1 < N) //ㅓ
{
ans = max(ans, (mymap[y - 1][x] + mymap[y][x] + mymap[y][x - 1] + mymap[y + 1][x]));
}
if (0 <= y - 1 && 0 <= x - 1 && x + 1 < M) //ㅗ
{
ans = max(ans, (mymap[y - 1][x] + mymap[y][x - 1] + mymap[y][x] + mymap[y][x + 1]));
}
if (0 <= x - 1 && x + 1 < M && y + 1 < N) //ㅜ
{
ans = max(ans, (mymap[y][x - 1] + mymap[y][x] + mymap[y][x + 1] + mymap[y + 1][x]));
}
}
}
cout << ans;
}
06-2 감시 ( 15683 )
- 첫째 줄에 사각 지대의 최소 크기를 출력한다
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int arr[8][8];
vector<pair<int, int>> cctv; // CCTV의 위치를 저장할 벡터
int ans = 987654321; // 최소로 막아야 할 칸의 수
int dy[4] = { 0, -1, 0, 1 }; // 방향에 따른 y좌표 변화량
int dx[4] = { 1, 0, -1, 0 }; // 방향에 따른 x좌표 변화량
// CCTV가 볼 수 있는 영역을 체크하는 함수
void check(int x, int y, int dir)
{
dir %= 4; // dir이 4보다 큰 경우를 위해 나머지 연산으로 방향을 구함
while (1)
{
int nx = x + dx[dir]; // 현재 위치에서 방향에 따라 이동한 x좌표
int ny = y + dy[dir]; // 현재 위치에서 방향에 따라 이동한 y좌표
x = nx; // 다음 위치로 x좌표 갱신
y = ny; // 다음 위치로 y좌표 갱신
if (nx < 0 || ny < 0 || M <= nx || N <= ny) return; // 범위를 벗어난 경우 반환
if (arr[ny][nx] == 6) return; // 벽인 경우 반환
if (arr[ny][nx] != 0) continue; // 이미 CCTV가 있거나, 이미 감시되는 영역인 경우 넘어감
arr[ny][nx] = -1; // CCTV로부터 감시되는 영역이므로 -1로 표시
}
}
// 모든 CCTV를 처리하는 dfs 함수
void dfs(int idx)
{
// 모든 CCTV를 처리한 경우
if (idx == cctv.size())
{
int cnt = 0; // 막아야 할 칸의 수를 세기 위한 변수
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (!arr[i][j]) cnt++; // CCTV로부터 감시되지 않는 영역의 개수를 센다
ans = min(ans, cnt); // 최소값 갱신
return;
}
int y = cctv[idx].first;
int x = cctv[idx].second;
for (int dir = 0; dir < 4; dir++)
{
int tmp[8][8];
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
tmp[i][j] = arr[i][j];
if (arr[y][x] == 1)
check(x, y, dir);
else if (arr[y][x] == 2)
{
check(x, y, dir);
check(x, y, dir + 2);
}
else if (arr[y][x] == 3)
{
check(x, y, dir);
check(x, y, dir + 1);
}
else if (arr[y][x] == 4)
{
check(x, y, dir);
check(x, y, dir + 1);
check(x, y, dir + 2);
}
else if (arr[y][x] == 5)
{
check(x, y, dir);
check(x, y, dir + 1);
check(x, y, dir + 2);
check(x, y, dir + 3);
}
dfs(idx + 1);
// case 종료이므로 초기화
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
arr[i][j] = tmp[i][j];
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> arr[i][j];
if (arr[i][j] != 0 && arr[i][j] != 6)
cctv.push_back({ i, j });
}
}
dfs(0);
cout << ans << '\n';
return 0;
}
06-3 치킨 배달 ( 15686 )
- 첫째 줄에 사각 지대의 최소 크기를 출력한다
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 50;
const int INF = 987654321;
int N, M;
int result = INF;
int graph[MAX][MAX]; // 치킨 거리를 계산하기 위한 그래프
vector<pair<int, int>> house, chicken; // 집과 치킨집 위치를 저장하는 벡터
bool live[13]; // 치킨집을 선택했는지 여부를 저장하는 배열
int distance(pair<int, int> a, pair<int, int> b) // 두 위치 사이의 거리를 계산하는 함수
{
return abs(a.first - b.first) + abs(a.second - b.second);
}
void DFS(int idx, int selected) // 치킨집을 선택하는 모든 경우의 수를 탐색하는 함수
{
if (selected == M) // 선택한 치킨집의 개수가 M개일 경우
{
int tempResult = 0;
for (int i = 0; i < house.size(); i++) // 모든 집에 대해
{
int dist = INF;
for (int j = 0; j < chicken.size(); j++) // 선택한 치킨집 중 가장 가까운 거리를 찾음
{
if (live[j])
dist = min(dist, distance(house[i], chicken[j]));
}
tempResult = tempResult + dist; // 가장 가까운 거리를 더해줌
}
result = min(result, tempResult); // 최소값을 갱신
return;
}
if (idx == chicken.size()) // 탐색이 끝났을 경우
return;
//프랜차이즈 선정
live[idx] = true; // 현재 치킨집을 선택함
DFS(idx + 1, selected + 1); // 다음 치킨집을 선택하기 위해 DFS 호출
//프랜차이즈 선정 X
live[idx] = false; // 현재 치킨집을 선택하지 않음
DFS(idx + 1, selected); // 다음 치킨집을 선택하기 위해 DFS 호출
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) // 입력받은 그래프를 저장하고, 집과 치킨집의 위치를 벡터에 저장
for (int j = 0; j < N; j++)
{
cin >> graph[i][j];
if (graph[i][j] == 1)
house.push_back({ i, j });
else if (graph[i][j] == 2)
chicken.push_back({ i, j });
}
DFS(0, 0); // 치킨집 선택을 위한 DFS 호출
cout << result << "\n"; // 최소 치킨 거리 출력
return 0;
}
06-4 야구 ( 17281 )
- 아인타팀이 얻을 수 있는 최대 점수를 출력한다
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int main(void)
{
// 선수 번호는 0 ~ 8로 하여 배열 접근이 쉽게 한다.
int N;
vector<vector<int>> score(50, vector<int>(9)); // 각 이닝의 선수별 타격 결과를 저장하는 벡터
int ans = 0; // 최대 점수를 저장할 변수
vector<int> player = { 1, 2, 3, 4, 5, 6, 7, 8 }; // 타자 순서를 저장하는 벡터
cin >> N; // 이닝의 수를 입력 받음
for (int i = 0; i < N; i++)
{
for (int j = 0; j < 9; j++)
{
cin >> score[i][j]; // 각 이닝의 각 선수의 결과를 입력 받음
}
}
do
{
int sum = 0; // 현재 순서로 게임을 진행했을 때의 총 점수
int index = 0; // 현재 타자의 인덱스
vector<int> tmp_player = player; // 현재 순서로 타자를 저장할 벡터
// 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다
// player 선언한 부분을 보면 8명의 선수밖에 등록 안되어 있는것을 확인할 수 있다
tmp_player.insert(tmp_player.begin() + 3, 0);
for (int inning = 0; inning < N; inning++)
{
queue<int> base; // 베이스에 있는 주자를 관리하는 큐
int out = 0; // 현재 이닝의 아웃 수
while (out != 3) // 아웃 수가 3이 될 때까지 반복
{
// 각 이닝 당 타순에 맞게 결과를 저장.
int state = score[inning][tmp_player[index++]];
if (state == 0)
{
out++; // 아웃
}
else if (state == 1)
{
// 안타
// 큐가 비어있으면 1루에 주자 1명을 두고, 2, 3루는 비어둔다.
// 큐가 비어있지 않으면 큐의 사이즈가 3인지 검사.
// 사이즈가 3인 경우 베이스를 1루씩 앞당기면서 베이스의 선수 여부에 따라 점수를 더해준다.
// 사이즈가 3이 아닌 경우 1을 푸시하여 1루에 진루.
if (base.empty())
{
base.push(0);
base.push(0);
base.push(1);
}
else
{
if (base.size() == 3)
{
sum += base.front();
base.pop();
}
base.push(1);
}
}
else if (state == 2)
{
// 2루타
// 큐가 비어있으면 2루에 주자 1명을 두고, 1, 3루는 비어둔다.
// 큐가 비어있지 않으면 큐의 사이즈가 3인지 검사.
// 사이즈가 3인 경우 베이스를 2루씩 앞당기면서 베이스의 선수 여부에 따라 점수를 더해준다.
// 사이즈가 3이 아닌 경우 1과 0을 푸시하여 2루에 선수 1명을 진루시키고, 1루에는 주자가 없다.
if (base.empty())
{
base.push(0);
base.push(1);
base.push(0);
}
else
{
if (base.size() == 3)
{
for (int i = 0; i < 2; i++)
{
sum += base.front();
base.pop();
}
}
base.push(1);
base.push(0);
}
}
else if (state == 3)
{
// 3루타
// 큐가 비어있으면 3루에 주자 1명을 두고, 1, 2루는 비어둔다.
// 큐가 비어있지 않으면 사이즈가 3인지 검사.
// 사이즈가 3인 경우 베이스를 3루씩 앞당기면서 베이스의 선수 여부에 따라 점수를 더해준다.
// 사이즈가 3이 아닌 경우 1, 0, 0을 푸시하여 3루에 선수 1명 진루, 1, 2루에는 주자가 없다.
if (base.empty())
{
base.push(1);
base.push(0);
base.push(0);
}
else
{
if (base.size() == 3)
{
for (int i = 0; i < 3; i++)
{
sum += base.front();
base.pop();
}
}
base.push(1);
base.push(0);
base.push(0);
}
}
else if (state == 4)
{
// 홈런
// 모든 주자가 들어와야 하기 때문에 큐가 빌 때까지 베이스의 선수 여부에 따라 점수를 더해준다.
// 큐가 비게되면 홈런을 친 선수의 점수까지 더해주는 ++을 진행.
while (!base.empty())
{
sum += base.front();
base.pop();
}
sum++;
}
if (index == 9) index = 0;
}
}
//모든 타순을 다르게 하여 최대값을 얻는 점수를 저장.
ans = ans < sum ? sum : ans;
} while (next_permutation(player.begin(), player.end()));
cout << ans;
return 0;
}
// https://codingnotes.tistory.com/113 킵 해두자
06-5 배열 돌리기 4 ( 17406 )
- 배열 A의 값의 최솟값을 출력한다
#include <iostream>
#include <algorithm> // min
#include <vector>
using namespace std;
struct Roll
{
int row, col, size;
};
int N, M, K;
int grid[51][51];
int copiedGrid[51][51]; // Copy of the grid for simulation
vector<Roll> operations;
int order[6]; // Order of rotation operations
bool isChosen[6]; // Indicates if a rotation operation is chosen
int minValue = 987654321;
void performRoll(int row, int col, int size)
{
for (int d = 1; d <= size; d++)
{
int start_x = col - d;
int start_y = row - d;
int end_x = col + d;
int end_y = row + d;
int tmp = copiedGrid[start_y][start_x];
// Left side
for (int i = start_y; i < end_y; i++)
copiedGrid[i][start_x] = copiedGrid[i + 1][start_x];
// Bottom side
for (int j = start_x; j < end_x; j++)
copiedGrid[end_y][j] = copiedGrid[end_y][j + 1];
// Right side
for (int i = end_y; start_y < i; i--)
copiedGrid[i][end_x] = copiedGrid[i - 1][end_x];
// Top side
for (int j = end_x; start_x < j; j--)
copiedGrid[start_y][j] = copiedGrid[start_y][j - 1];
copiedGrid[start_y][start_x + 1] = tmp;
}
}
void simulate()
{
int result = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
copiedGrid[i][j] = grid[i][j];
// Perform rotation operations in the specified order
for (int i = 0; i < K; i++)
{
int operationIdx = order[i];
int row = operations[operationIdx].row;
int col = operations[operationIdx].col;
int size = operations[operationIdx].size;
performRoll(row, col, size);
}
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
result += copiedGrid[i][j];
minValue = min(minValue, result);
result = 0;
}
}
void dfs(int count)
{
if (count == K)
{
simulate();
return;
}
for (int i = 0; i < K; i++)
{
if (isChosen[i]) continue;
order[count] = i;
isChosen[i] = true;
dfs(count + 1);
isChosen[i] = false;
}
}
void solve()
{
cin >> N >> M >> K;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
cin >> grid[i][j];
}
for (int i = 0; i < K; i++)
{
int row, col, size;
cin >> row >> col >> size;
operations.push_back({ row, col, size });
}
dfs(0);
cout << minValue << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}
// https://11001.tistory.com/30
// https://jaimemin.tistory.com/1482
Chapter 07 DP
07-1 문제
- 설명
댓글남기기