#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> cows(n); // {소의 위치, 소의 원래 인덱스}
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cows[i] = { x, i };
}
sort(cows.begin(), cows.end()); // 소의 위치를 기준으로 정렬
vector<int> to(n); // 각 소가 공을 전달할 소의 인덱스
vector<int> indegree(n); // 각 소의 진입 차수
for (int i = 0; i < n; i++) {
int left_dist = INT_MAX;
int right_dist = INT_MAX;
if (i > 0) {
left_dist = cows[i].first - cows[i - 1].first;
}
if (i < n - 1) {
right_dist = cows[i + 1].first - cows[i].first;
}
if (left_dist <= right_dist) {
// 왼쪽 소에게 전달
to[i] = i - 1;
}
else {
// 오른쪽 소에게 전달
to[i] = i + 1;
}
// 공을 받는 소의 진입 차수 증가
indegree[to[i]]++;
}
// 초기 공을 받아야 하는 소의 수 계산
int balls = 0;
vector<bool> visited(n, false);
// 진입 차수가 0인 소들을 방문하여 도달할 수 있는 모든 소들을 방문 표시
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
balls++;
int curr = i;
while (!visited[curr]) {
visited[curr] = true;
curr = to[curr];
}
}
}
// 아직 방문하지 않은 소들을 탐색하여 사이클을 찾음
for (int i = 0; i < n; i++) {
if (!visited[i]) {
balls++; // 사이클마다 공 하나 추가
int curr = i;
while (!visited[curr]) {
visited[curr] = true;
curr = to[curr];
}
}
}
cout << balls << endl;
return 0;
}
소들은 소풍을 가고 싶어 합니다! Farmer John의 K마리 소들은 각각 N개의 목초지 중 한 곳에서 풀을 뜯고 있습니다. 목초지는 1번부터 N번까지 번호가 매겨져 있으며, 일방통행 경로 M개로 연결되어 있습니다(경로는 자기 자신을 연결하는 경우는 없습니다).
소들은 동일한 목초지에서 만나 소풍을 가고 싶어 하지만, 일방통행 경로로 인해 어떤 소들은 특정 목초지로만 갈 수 있을 수도 있습니다. 모든 소들이 도달할 수 있는 목초지가 몇 개인지 찾아서 소들이 만날 수 있는 소풍 장소를 정해주세요.
입력
1번째 줄: 세 개의 정수 K, N, M이 공백으로 구분되어 주어집니다. (1 ≤ K ≤ 100, 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000)
2번째 줄부터 K개의 줄: 각 줄은 소들이 있는 목초지 번호가 하나씩 주어집니다. 이 목초지 번호는 1부터 N까지의 숫자입니다.
K+2번째 줄부터 M+K+1번째 줄: 각 줄에는 두 개의 정수 A와 B가 주어지며, 이는 목초지 A에서 목초지 B로 가는 일방통행 경로가 있음을 나타냅니다. (1 ≤ A, B ≤ N, A ≠ B)
출력
모든 소들이 일방통행 경로를 통해 도달할 수 있는 목초지의 수를 출력하세요.
#문제 간단 정리
그래프 탐색문제
말 그대로 각 소들이 전부 방문하는 목초지의 개수를 찾아주면 된다
#문제 해결 방법
나는 각 소 들을 2차원 배열로
방문배열로 만들어줬고
방문여부는 dfs로 탐색하였다
그리고 각 목초지에 모든소가 방문하는지 탐색해주면 된다.
#전체 코드
#include <iostream>
#include <vector>
using namespace std;
int k, n, m;
vector<vector<int>> graph;
vector<int> cowPos;
vector<vector<bool>> check;
void dfs(int cowNum, int index) {
for (auto a : graph[index]) {
if (!check[cowNum][a]) {
check[cowNum][a] = true;
dfs(cowNum, a);
}
}
}
int main() {
cin >> k >> n >> m;
check.resize(k, vector<bool>(n, false));
for (int i = 0; i < k; i++) {
int input;
cin >> input;
cowPos.push_back(input - 1);
}
graph.resize(n);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a - 1].push_back(b - 1);
}
for (int i = 0; i < k; i++) {
int cp = cowPos[i];
check[i][cp] = true;
dfs(i, cp);
}
int ans = 0;
for (int i = 0; i < n; i++) {
bool all_cows_can_reach = true;
for (int j = 0; j < k; j++) {
if (!check[j][i]) {
all_cows_can_reach = false;
break;
}
}
if (all_cows_can_reach) ans++;
}
cout << ans << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <cmath>
using namespace std;
vector<vector<int>> board;
pair<int, int> prof, sung;
int n;
// 학생을 세는 함수
bool CountingStudents(int ys, int ye, int xs, int xe, bool sameLine) {
int count = 0;
if (sameLine) {
// 같은 행 또는 같은 열일 경우
if (xs == xe) { // 같은 행
for (int j = ys; j <= ye; j++) {
if (board[xs][j] == 1) {
count++;
}
}
} else { // 같은 열
for (int i = xs; i <= xe; i++) {
if (board[i][ys] == 1) {
count++;
}
}
}
} else {
// 직사각형 내 모든 셀
for (int i = xs; i <= xe; i++) { // 행 반복
for (int j = ys; j <= ye; j++) { // 열 반복
if (board[i][j] == 1) {
count++;
}
}
}
}
return count >= 3;
}
int main() {
cin >> n;
board.resize(n, vector<int>(n));
// 입력 받기 및 교수님과 성규의 위치 찾기
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
if (board[i][j] == 5) prof = {i, j};
if (board[i][j] == 2) sung = {i, j};
}
}
// 거리 계산 (제곱 거리 사용)
int dist = pow(abs(sung.first - prof.first), 2) + pow(abs(sung.second - prof.second), 2);
if (dist >= 25) {
// 교수님과 성규의 위치를 기준으로 직사각형 정의
int xs = min(prof.first, sung.first);
int xe = max(prof.first, sung.first);
int ys = min(prof.second, sung.second);
int ye = max(prof.second, sung.second);
// 같은 행 또는 같은 열인지 확인
bool sameLine = false;
if (prof.first == sung.first || prof.second == sung.second) {
sameLine = true;
}
// 학생 수 세기
if (CountingStudents(ys, ye, xs, xe, sameLine)) {
cout << 1 << '\n';
return 0;
} else {
cout << 0 << '\n';
return 0;
}
} else {
cout << 0 << '\n';
return 0;
}
return 0;
}
화폐 시스템 S는 실제 또는 가상의 화폐 시스템에서 동전의 값을 나타내는 고유한 양의 정수들의 유한 집합(비어있지 않은 집합)입니다. 예를 들어, 캐나다에서 사용되는 화폐 시스템은 {1, 5, 10, 25, 100, 200}으로, 1은 1센트 동전을 나타내고 200은 2달러(200센트)를 나타냅니다. 우리는 동전이 무한히 많다고 가정하며, S에는 항상 1이 포함된다고 가정합니다. 1이 포함된다는 것은 모든 양의 정수를 동전들의 합으로 표현할 수 있음을 보장합니다.
전 세계의 계산원들은 다음과 같은 문제에 직면합니다: 주어진 화폐 시스템과 고객에게 갚아야 할 양의 정수 금액이 있을 때, 정확히 그 금액을 맞추기 위해 필요한 최소 동전의 수는 얼마인가? 예를 들어, 캐나다의 계산원이 고객에게 83센트를 갚아야 한다고 가정합시다. 한 가지 가능한 방법은 25+25+10+10+10+1+1+1, 즉 8개의 동전을 주는 것이지만, 이는 최적의 방법이 아닙니다. 계산원은 25 + 25 + 25 + 5 + 1 + 1 + 1로 7개의 동전을 줄 수 있으며, 이 방법이 최적입니다.
다행히도, 캐나다 화폐 시스템은 탐욕 알고리즘이 항상 최적의 해를 제공하는 성질을 가지고 있습니다. 탐욕 알고리즘은 반복적으로 남은 금액보다 작거나 같은 가장 큰 값을 가진 동전을 선택하는 방식으로 진행합니다. 탐욕 알고리즘이 항상 최적의 해를 제공하는 화폐 시스템을 '정식(canonical)' 화폐 시스템이라고 부릅니다.
여러분의 도전 과제는 다음과 같습니다: 주어진 화폐 시스템 S = {c1, c2, ..., cn}에 대해 S가 정식인지 비정식(non-canonical)인지 판단하는 것입니다. 만약 S가 비정식이라면, 최소한 하나의 반례가 존재하며, 이는 탐욕 알고리즘으로 구한 동전 개수가 최적의 동전 개수보다 많아지는 양의 정수 x입니다.
입력:
입력은 하나의 경우로 구성됩니다. 첫 번째 줄에는 동전 종류의 수 n (2 ≤ n ≤ 100)이 주어집니다. 다음 줄에는 n개의 동전 값 c1 c2 ... cn이 공백으로 구분되어 주어지며, c1 = 1이고 c1 < c2 < ... < cn ≤ 10^6입니다.
출력:
화폐 시스템이 정식이면 "canonical"을, 비정식이면 "non-canonical"을 출력하세요.
#문제 간단 정리
그리디 + dp 를 구현하라
#문제 해결 방법
우선 딱 보면 알수 있겟지만
그리디를 구현하고
dp를 통한 최적해를 통해서
둘을 비교하면 얻을 수 있다는 것을 알 수 있다.
그리디는 쉽게 구현할 수 있으니 넘어가고
dp는 배낭문제와 같은데
dp[i]는 금액 i을 만들기 위한 최소 동전 수
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
의 점화식을 갖는다
그리고
확인하는 최대 금액이 어째서
int max_x = coins[n-2] + coins[n-1];
인지가 중요한거 같은데
지문에
An example of a non-canonical coin system is {1, 3, 4}, for which 6 is a counterexample, since the greedy algorithm yields 4 + 1 + 1 (3 coins), but an optimal solution is 3 + 3 (2 coins). A useful fact (due to Dexter Kozen and Shmuel Zaks) is that if S is noncanonical, then the smallest counterexample is less than the sum of the two largest denominations.
라고 나와있는데
"예를 들어, {1, 3, 4}라는 비정식(non-canonical) 화폐 시스템에서는 6이 반례(counterexample)가 됩니다. 탐욕 알고리즘을 사용하면 4 + 1 + 1, 즉 3개의 동전이 사용되지만, 최적의 해법은 3 + 3으로 2개의 동전만 필요합니다. Dexter Kozen과 Shmuel Zaks에 따르면, 화폐 시스템이 비정식이라면 가장 작은 반례는 두 개의 가장 큰 동전 값의 합보다 작다는 유용한 사실이 있습니다."
라고 잘 나와잇다.
#전체 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
vector<int> coins;
int greedy(int value,vector<int> &coins) {
int count = 0;
int remaining = value;
for (int i = coins.size() - 1; i >= 0; i--) {
if (coins[i] <= remaining) {
int num = remaining / coins[i];
count += num;
remaining -= coins[i] * num;
}
if (remaining == 0) {
break;
}
}
return count;
}
int main() {
int n;
cin >> n;
coins.resize(n);
for (int i = 0; i < n; i++) {
cin >> coins[i];
}
sort(coins.begin(), coins.end());
int max_x = coins[n - 2] + coins[n - 1];
vector<int> dp(max_x + 1, max_x + 1);
dp[0] = 0;
for (int i = 1; i <= max_x; i++) {
for (int j = 0; j < n; j++) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
else {
break;
}
}
}
bool isCanonical = true;
for (int x = 1; x <= max_x; ++x) {
int greedy_count = greedy(x, coins);
if (greedy_count > dp[x]) {
isCanonical = false;
break;
}
}
if (isCanonical) {
cout << "canonical" << '\n';
}
else {
cout << "non-canonical" << '\n';
}
return 0;
}
Bobby는 새 회사에 입사했고, 인사팀에서 그의 생일을 사무실 달력에 기록하도록 요청했습니다. Bobby the Birthday Boy는 특별하게 느끼고 싶어 합니다! 또한, Bobby the Birthday Boy는 주목받기 위해 거짓말을 하는 것을 꺼려하지 않습니다.
그는 사람들이 생일을 축하하지 않거나 케이크를 먹지 않은 기간이 길어질수록 새로운 생일이 찾아올 때 더 좋아한다는 것을 알아챘습니다. 그래서 가능한 한 긴 생일이 없는 기간이 막 끝난 시점에 자신의 생일을 정하고 싶어 합니다. 물론, 그는 동료들과 생일을 공유하고 싶지 않습니다.
Bobby가 가능한 한 특별하게 느낄 수 있도록 가짜 생일을 만들어 줄 수 있나요? Bobby는 윤년에 신경 쓰지 않습니다: 모든 해가 윤년이 아니며, 아무도 2월 29일에 생일이 없다고 가정할 수 있습니다. 만약 여러 날짜가 동일한 경우, Bobby는 현재 날짜인 10월 27일 직후에 오는 날짜를 선택하기로 결정했습니다. 이는 가능한 한 빨리 생일을 축하할 수 있기 때문입니다.
입력
첫 줄에 1 ≤ n ≤ 100, Bobby가 새 사무실에 있는 동료의 수가 주어집니다.
그 다음 n개의 줄이 이어지며, 각 줄은 한 동료에 해당합니다. 각 줄은 동료의 이름(최대 20개의 대소문자)과 생일 날짜가 공백으로 구분되어 주어집니다. 날짜는 mm-dd 형식입니다.
출력
Bobby가 선택한 가짜 생일 날짜(mm-dd 형식)를 출력하세요.
#문제 간단 정리
구현 + 시뮬레이션 문제
#문제 해결 방법
구현 시뮬레이션 문제이기 때문에 지문 그대로 구현하면 된다만..
예외 조건이 은근 있기 때문에 신경써야된다.
우선 입력에서 파싱을 사용해서 입력받아야되는걸 생각하고
// 동료들의 생일을 일수로 변환하여 저장 for(int i = 0; i < n; i++) { string name, day; cin >> name >> day; int month = stoi(day.substr(0, 2)); int d = stoi(day.substr(3, 2)); dayto365.push_back(makeDays(month, d)); }
// 날짜를 일수로 변환하는 함수 (1~365) int makeDays(int month, int day) { int result = 0; for(int i = 0; i < month - 1; i++) { result += daysInMonth[i]; } result += day; return result; }
// 일수를 "mm-dd" 형식으로 변환하는 함수 string day_to_date(int day_number) { int month = 1; while(day_number > daysInMonth[month - 1]) { day_number -= daysInMonth[month - 1]; month++; } // 월과 일을 두 자리로 포맷팅 string mm = (month < 10 ? "0" : "") + to_string(month); string dd = (day_number < 10 ? "0" : "") + to_string(day_number); return mm + "-" + dd; }
여기서 중요한건 각 월을 배열로 저장해줘야 환산이 쉬워진다.
자 그렇다면 이렇게 환산한날들을 정렬해주고
// 생일을 정렬 sort(dayto365.begin(), dayto365.end());
// 연말을 넘어가는 경우를 처리하기 위해 첫 번째 생일에 365를 더해 추가 dayto365.push_back(dayto365[0] + 365);
자 for 문을 돌면서 i-1 번째랑 비교해서 그 간격을 조사할건데
첫번째 인덱스 0 번은 i-1 번이 없기 때문에 365 를 더해서 뒤로 더해준다.
이렇게하면 전부 비교가 가능하다
int maxGap = -1; vector<int> candidates;
// 가장 긴 간격을 찾고, 그 간격의 끝날(다음 생일 전날)을 후보로 추가 for(int i = 1; i < dayto365.size(); i++) { int tempGap = dayto365[i] - dayto365[i - 1] - 1; // 생일 사이의 기간
// 현재 날짜인 10월 27일의 일수 int the1027 = makeDays(10, 27);
// 후보 날짜 중 10월 27일 이후의 날짜를 찾기 위한 처리 vector<int> after1027; for(auto date : candidates){ if(date > the1027){ after1027.push_back(date); } else{ after1027.push_back(date + 365); // 연말을 넘어가는 경우 처리 } }
int selected_date; if(!after1027.empty()){ // 10월 27일 이후의 날짜 중 가장 빠른 날짜 선택 selected_date = *min_element(after1027.begin(), after1027.end()); } else{ // 없다면 모든 후보 중 가장 빠른 날짜 선택 selected_date = *min_element(candidates.begin(), candidates.end()); }
이제 후보 날짜를 처리해 줄건데(동점인경우)
10/27일을 365단위로 환산해두고 일단
10/27일보다 작은경우 365를 더해서 벡터에 넣어준다.
int selected_date; if(!after1027.empty()){ // 10월 27일 이후의 날짜 중 가장 빠른 날짜 선택 selected_date = *min_element(after1027.begin(), after1027.end()); } else{ // 없다면 모든 후보 중 가장 빠른 날짜 선택 selected_date = *min_element(candidates.begin(), candidates.end()); }
"직사각형 격자에 살아있는 셀과 죽은 셀이 있고, 모든 셀이 동시에 정해진 시계 틱에 따라 다음 세대의 셀 상태로 업데이트되는 그 게임 말하는 거지? 죽은 셀이 정확히 세 개의 살아있는 이웃을 가질 때 다음 세대에 살아있게 되고, 살아있는 셀이 이웃이 두 개 미만 또는 세 개 초과일 때 다음 세대에 죽게 되며, 다른 셀들은 상태가 변하지 않는 그 게임 말하는 거야?"
"응, 맞아. 내가 그걸 프로그래밍하려고 애쓰고 있는데..."
"대수롭지 않게 – 누구나 했잖아!"
"잠깐만, 내가 끝내게 – 극좌표 그래프 용지에서 작동하도록 프로그래밍하려고 해, 이렇게:"
"음. 진짜 곰처럼 보이네."
"나쁘지 않아 – 대부분의 셀은 Game of Life와 마찬가지로 여덟 개의 이웃을 가져. 외곽과 중심의 쐐기 모양 셀들이 까다로운데, 그건 처리할 방법을 찾았어. 반지름의 수가 짝수이면, 외곽과 내곽의 모든 셀은 여덟 개의 이웃을 가져: 링 위의 다섯 개의 일반 이웃과 가장 가까운 인접 링의 이웃, 그리고 그리드에서 지름상 반대편에 있는 셀, 그리고 그 셀의 왼쪽과 오른쪽 이웃. 예를 들어:"
"A의 이웃은 1번부터 8번까지의 셀이고, B의 이웃은 p부터 w까지의 셀이다."
"그렇다면 반지름의 수가 홀수일 때는 어떻게 해?"
"묻지 마."
입력
입력은 여러 개의 문제 인스턴스로 구성됩니다. 각 문제 인스턴스는 두 개의 양의 정수 m과 n으로 시작합니다. 여기서 m은 링의 수 (3 ≤ m ≤ 100), n은 반지름의 수 (6 ≤ n ≤ 100)이며, n은 항상 짝수입니다. 그 다음에 양의 정수 k와 k개의 서로 다른 쌍의 양의 정수가 주어지며, 이는 살아있는 셀의 위치를 나타냅니다. 첫 번째 정수는 링을 나타내며, 바깥 링부터 안쪽으로 0부터 시작합니다. 두 번째 정수는 해당 링에서의 셀 번호를 나타내며, 0부터 시계 방향으로 주어집니다 (시작 반지름은 임의의 고정된 반지름 선에서 시작). 그 다음에 비음수 정수 g (0 ≤ g ≤ 500)가 주어지며, 이는 세대 수를 나타냅니다. 마지막 테스트 케이스 뒤에는 두 개의 0이 주어집니다.
출력
각 테스트 케이스에 대해 테스트 케이스 번호와 다섯 개의 정수를 출력합니다: g번의 반복 후 살아있는 셀의 수, 첫 번째 살아있는 셀의 위치 (r1 c1), 마지막 살아있는 셀의 위치 (r2 c2). 여기서 첫 번째와 마지막은 살아있는 셀들을 링 번호와 셀 번호의 사전순으로 정렬했을 때의 첫 번째와 마지막을 의미합니다. 살아있는 셀이 없을 경우, 0 -1 -1 -1 -1을 출력합니다.
#문제 간단 정리
구현 + 시뮬레이션
사실상 지문 그대로 구현하면 된다.
#문제 해결 방법
문제이해:
이건 game of life 라는걸 다른버전으로 구현하는 것인데
아는사람이라면 반갑게 볼수 있다.
자 이 문제를 보자면
각 칸에 생존 혹은 사망 상태가 있고
시간이 지날때 주위에 생존이 2개미만 3개 초과면
사망하고
생존이 없는 칸에서 주위에 생존한게 3개 있다면
그 칸은 살아나게 된다.
그리고 다른 셀들은 상태가 변하지 않는다.
여기서 하나 주의 해야 될건 주위에 2개가있다면 생존상태가 그대로 유지된다는 점을 유의하자
문제 설계:
자 구현문제이니 어떻게 구현할 것인지 설계하는게 중요하다
천천히 설계를 해 나가자
1.우선 각 라운드를 진행하기 위해서
시뮬레이팅 함수가 있으면 좋을것이다
simulated()
2.그리고 시뮬레이팅을 하려면 그 셀에 주위에 있는
셀을 카운팅하는 함수가 필요할 것이다.
findAround()
3. 그리고 출력하는데 있어서 첫번째 셀 그리고 마지막 셀을 찾아서 출력하는 함수가 필요할 것이다.
resultCells()
자 그렇다면 우리는
main(){
simulated(){
findAround()
}
resultCells()
}
대략 이런식으로 구성될거라 생각 할 수 있고
polar를 구현할 자료구조로는
링이 하나씩 있고 링에 각 셀이 원형으로 포함되어있으니
이차원 벡터 혹은 배열이 좋을 것이다.
그리고 구현하기전에 생각해보자면 원형이기때문에 모듈러 연산을 활용하는 것이 좋을 것같다.
int m, n;
vector<pair<int, int>> cells;
vector<vector<int>> polar;
int main() {
int t = 0;
while (true) {
cin >> m >> n;
if (n == 0 && m == 0) {
return 0;
}
t++;
polar.assign(m ,vector<int>(n,0));
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int ring, cell;
cin >> ring >> cell;
polar[ring][cell] = 1; //살아있음
}
int g;
cin >> g;
//g 만큼 시뮬레이션 진행
simulate(g);
//결과 출력
resultCells(t);
}
return 0;
}
자 우선 입력과 메인함수 플로우를 보자면 이렇게 될 것이다.
그렇다면 시뮬레이팅 함수와 시뮬레이팅함수가 사용할 주변 셀 탐색 함수 를 만들자
void simulate(int g) {
for (int p = 0; p < g; p++) {
//변경을 저장할 임시 벡터
vector<vector<int>> polarCopy = polar;
//모든셀 조회
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 그 주위 살아있는 셀 몇개 인지 조회
int aroundLiveCells = findAround(i, j);
if (polar[i][j] == 1) { // 현재 셀이 살아있는 경우
if (aroundLiveCells < 2 || aroundLiveCells > 3) {
polarCopy[i][j] = 0;
}
}
else { // 현재 셀이 죽어있는 경우
if (aroundLiveCells == 3) {
polarCopy[i][j] = 1;
}
}
//cout << aroundLiveCells << ' ';
}
}
polar = polarCopy;
}
}
우선 시뮬레이팅 함수는 쉽게 구현 할 수 있다.
자그럼 탐색함수가 관건인데 모듈러 연산을 사용하는걸 주의하자
// 주위 셀 조사 함수
int findAround(int ring, int cell) {
int cellCount = 0;
int half = n / 2; // 반대편 셀을 찾기 위한 반
// 링의 이전 링, 현재 링, 다음 링을 탐색 (-1, 0, 1)
for (int i = -1; i <= 1; i++) { // 링 방향
for (int j = -1; j <= 1; j++) { // 셀 방향
if (i == 0 && j == 0) continue; // 자기 자신은 제외
int nextRing = ring + i;
int nextCell = (cell + j + n) % n; // 셀 번호는 모듈로 연산으로 순환
if (nextRing >= 0 && nextRing < m) { // 링 범위 내인지 확인
if (polar[nextRing][nextCell] == 1) {
cellCount++;
}
}
else {
// 반대편 셀을 체크
int oppositeCell = (nextCell + half + n) % n;
if (polar[ring][oppositeCell] == 1) {
cellCount++;
}
}
}
}
return cellCount;
}
void resultCells(int testCase) {
int cellCount = 0;
pair<int, int> first = { -1, -1 };
pair<int, int> last = { -1, -1 };
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (polar[i][j] == 1) {
cellCount++;
if (first.first == -1) { // 첫 번째 생존 셀 설정
first = { i, j };
}
last = { i, j }; // 마지막 생존 셀 계속 업데이트
}
}
}
cout << "Case " << testCase << ": ";
if (cellCount == 1) {
cout << cellCount << " " << 0 << " " << 0<< " "
<< last.first << " " << last.second << "\n";
}
else if (cellCount > 0) {
cout << cellCount << " " << first.first << " " << first.second << " "
<< last.first << " " << last.second << "\n";
}
else {
cout << "0 -1 -1 -1 -1\n";
}
}
출력함수는 쉽기때문에 여러방법으로 구현이 가능할 것이다.
#전체 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int m, n;
vector<pair<int, int>> cells;
vector<vector<int>> polar;
int findAround(int ring, int cell);
void simulate(int g) {
for (int p = 0; p < g; p++) {
//변경을 저장할 임시 벡터
vector<vector<int>> polarCopy = polar;
//모든셀 조회
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 그 주위 살아있는 셀 몇개 인지 조회
int aroundLiveCells = findAround(i, j);
if (polar[i][j] == 1) { // 현재 셀이 살아있는 경우
if (aroundLiveCells < 2 || aroundLiveCells > 3) {
polarCopy[i][j] = 0;
}
}
else { // 현재 셀이 죽어있는 경우
if (aroundLiveCells == 3) {
polarCopy[i][j] = 1;
}
}
//cout << aroundLiveCells << ' ';
}
}
polar = polarCopy;
}
}
// 주위 셀 조사 함수
int findAround(int ring, int cell) {
int cellCount = 0;
int half = n / 2; // 반대편 셀을 찾기 위한 반
// 링의 이전 링, 현재 링, 다음 링을 탐색 (-1, 0, 1)
for (int i = -1; i <= 1; i++) { // 링 방향
for (int j = -1; j <= 1; j++) { // 셀 방향
if (i == 0 && j == 0) continue; // 자기 자신은 제외
int nextRing = ring + i;
int nextCell = (cell + j + n) % n; // 셀 번호는 모듈로 연산으로 순환
if (nextRing >= 0 && nextRing < m) { // 링 범위 내인지 확인
if (polar[nextRing][nextCell] == 1) {
cellCount++;
}
}
else {
// 반대편 셀을 체크
int oppositeCell = (nextCell + half + n) % n;
if (polar[ring][oppositeCell] == 1) {
cellCount++;
}
}
}
}
return cellCount;
}
void resultCells(int testCase) {
int cellCount = 0;
pair<int, int> first = { -1, -1 };
pair<int, int> last = { -1, -1 };
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (polar[i][j] == 1) {
cellCount++;
if (first.first == -1) { // 첫 번째 생존 셀 설정
first = { i, j };
}
last = { i, j }; // 마지막 생존 셀 계속 업데이트
}
}
}
cout << "Case " << testCase << ": ";
if (cellCount == 1) {
cout << cellCount << " " << 0 << " " << 0<< " "
<< last.first << " " << last.second << "\n";
}
else if (cellCount > 0) {
cout << cellCount << " " << first.first << " " << first.second << " "
<< last.first << " " << last.second << "\n";
}
else {
cout << "0 -1 -1 -1 -1\n";
}
}
int main() {
int t = 0;
while (true) {
cin >> m >> n;
if (n == 0 && m == 0) {
return 0;
}
t++;
polar.assign(m ,vector<int>(n,0));
int k;
cin >> k;
cells.clear();
for (int i = 0; i < k; i++) {
int ring, cell;
cin >> ring >> cell;
cells.push_back({ ring,cell });
polar[ring][cell] = 1; //살아있음
}
int g;
cin >> g;
//g 만큼 시뮬레이션 진행
simulate(g);
//결과 출력
resultCells(t);
}
return 0;
}
