BOJ 17822 : 원판 돌리기 - C++
원판 돌리기
코드
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 1253 ~ 0304
int N,M,T,ans;
deque<pair<int,bool>> cycle[55];
int DirCntCalc(int dir, int cnt)
{
if(dir == 0) return cnt;
/* 개수가 고정이 아니기때문에 M-cnt로 해야한다 */
return M-cnt;
}
bool checkPos(int i)
{
if(i<1 or i>N) return false;
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> T;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
int a;
cin >> a;
cycle[i].push_back({a, false});
}
}
for(int n=1;n<=T;n++)
{
int ch, dir, cnt;
cin >> ch >> dir >> cnt;
/* 원판 회전 */
int res = DirCntCalc(dir,cnt); // 모두 시계방향으로 계산하기 위함
for(int size=ch;size<=N;size+=ch)
{
for(int i=0;i<res;i++)
{
int tmp = cycle[size].back().first;
cycle[size].pop_back();
cycle[size].push_front({tmp, false});
}
}
/* 인접한 수가 같은것이 있는지 검사 */
bool del = false;
int sum = 0;
int size = 0;
for(int i=1;i<=N;i++)
{
for(int j=0;j<M;j++)
{
int cur = cycle[i][j].first;
if(cur == -1e9) continue;
if(checkPos(i+1) and cur == cycle[i+1][j].first){
cycle[i+1][j].second = true;
cycle[i][j].second = true;
del = true;
}
if(checkPos(i-1) and cur == cycle[i-1][j].first){
cycle[i-1][j].second = true;
cycle[i][j].second = true;
del = true;
}
int nj = j+1;
if(nj >=M) nj -= M;
if(cur == cycle[i][nj].first){
cycle[i][nj].second = true;
cycle[i][j].second = true;
del = true;
}
nj = j-1;
if(nj < 0) nj += M;
if(cur == cycle[i][nj].first){
cycle[i][nj].second = true;
cycle[i][j].second = true;
del = true;
}
}
}
/* true로 체크된 수 삭제하기 */
for(int i=1;i<=N;i++)
{
for(int j=0;j<M;j++)
{
if(cycle[i][j].first == -1e9) continue;
if(cycle[i][j].second == true)
cycle[i][j].first = -1e9;
if(cycle[i][j].first != -1e9){
sum += cycle[i][j].first;
size++;
}
}
}
/* 인접한 것이 없어서 숫자를 지우지 않았다면 */
if(del == false)
{
double avg = sum/(double)size;
sum=0;
for(int i=1;i<=N;i++)
{
for(int j=0;j<M;j++)
{
if(cycle[i][j].first == -1e9) continue;
if(cycle[i][j].first > avg) cycle[i][j].first--;
else if(cycle[i][j].first < avg) cycle[i][j].first++;
sum += cycle[i][j].first;
}
}
}
ans = sum;
}
cout << ans;
return 0;
}
- 핵심
원판
을 회전
할 때 dir(방향)
과 횟수(cnt)
를 받아서 무조건 시계방향
으로 변환
하면 반시계방향 구현하지 않아도 됨
--> reverseDir
에서 주의할 것
은 M-cnt
로 해야한다! (1 Cycle
이 M에따라 바뀌기 때문에
)
인접한 수가 같은것이 있는지 검사
하는 과정에서 바로 값
을 바꾸면 안된다
--> 바로 인접한 값
들을 바꾸면
다음 검사
에 영향을 끼칠 수 있음
--> bool 변수
로 체크
만 하고 한번에 값
을 변경
해야 한다!!!
- 오래걸린 이유
: 인접한 수가 같은것이 있는지 검사
하면서 값을 바로 갱신
했더니 다음 수행
에 영향
을 끼쳐서 오작동
--> 값을 수정
할 때 다음 반복문
에 영향을 주는지
꼭 확인
하자.....
--> 안전하게 bool변수
로 체크
해서 한번에 변경
하자
Author And Source
이 문제에 관하여(BOJ 17822 : 원판 돌리기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-17822-원판-돌리기-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <deque> #include <numeric> #include <map> #define ll long long using namespace std; // 1253 ~ 0304 int N,M,T,ans; deque<pair<int,bool>> cycle[55]; int DirCntCalc(int dir, int cnt) { if(dir == 0) return cnt; /* 개수가 고정이 아니기때문에 M-cnt로 해야한다 */ return M-cnt; } bool checkPos(int i) { if(i<1 or i>N) return false; return true; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M >> T; for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { int a; cin >> a; cycle[i].push_back({a, false}); } } for(int n=1;n<=T;n++) { int ch, dir, cnt; cin >> ch >> dir >> cnt; /* 원판 회전 */ int res = DirCntCalc(dir,cnt); // 모두 시계방향으로 계산하기 위함 for(int size=ch;size<=N;size+=ch) { for(int i=0;i<res;i++) { int tmp = cycle[size].back().first; cycle[size].pop_back(); cycle[size].push_front({tmp, false}); } } /* 인접한 수가 같은것이 있는지 검사 */ bool del = false; int sum = 0; int size = 0; for(int i=1;i<=N;i++) { for(int j=0;j<M;j++) { int cur = cycle[i][j].first; if(cur == -1e9) continue; if(checkPos(i+1) and cur == cycle[i+1][j].first){ cycle[i+1][j].second = true; cycle[i][j].second = true; del = true; } if(checkPos(i-1) and cur == cycle[i-1][j].first){ cycle[i-1][j].second = true; cycle[i][j].second = true; del = true; } int nj = j+1; if(nj >=M) nj -= M; if(cur == cycle[i][nj].first){ cycle[i][nj].second = true; cycle[i][j].second = true; del = true; } nj = j-1; if(nj < 0) nj += M; if(cur == cycle[i][nj].first){ cycle[i][nj].second = true; cycle[i][j].second = true; del = true; } } } /* true로 체크된 수 삭제하기 */ for(int i=1;i<=N;i++) { for(int j=0;j<M;j++) { if(cycle[i][j].first == -1e9) continue; if(cycle[i][j].second == true) cycle[i][j].first = -1e9; if(cycle[i][j].first != -1e9){ sum += cycle[i][j].first; size++; } } } /* 인접한 것이 없어서 숫자를 지우지 않았다면 */ if(del == false) { double avg = sum/(double)size; sum=0; for(int i=1;i<=N;i++) { for(int j=0;j<M;j++) { if(cycle[i][j].first == -1e9) continue; if(cycle[i][j].first > avg) cycle[i][j].first--; else if(cycle[i][j].first < avg) cycle[i][j].first++; sum += cycle[i][j].first; } } } ans = sum; } cout << ans; return 0; }
- 핵심
원판
을회전
할 때dir(방향)
과횟수(cnt)
를 받아서무조건 시계방향
으로변환
하면반시계방향 구현하지 않아도 됨
-->reverseDir
에서주의할 것
은M-cnt
로 해야한다! (1 Cycle
이M에따라 바뀌기 때문에
)인접한 수가 같은것이 있는지 검사
하는 과정에서바로 값
을바꾸면 안된다
--> 바로인접한 값
들을바꾸면
다음 검사
에영향을 끼칠 수 있음
-->bool 변수
로체크
만 하고한번에 값
을변경
해야 한다!!!
- 오래걸린 이유
:인접한 수가 같은것이 있는지 검사
하면서값을 바로 갱신
했더니다음 수행
에영향
을 끼쳐서오작동
-->값을 수정
할 때다음 반복문
에영향을 주는지
꼭확인
하자.....
--> 안전하게bool변수
로체크
해서한번에 변경
하자
Author And Source
이 문제에 관하여(BOJ 17822 : 원판 돌리기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-17822-원판-돌리기-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)