인프런 커뮤니티 질문&답변
작성한 질문수
5-P 질문 있습니다.
작성
·
371
0
95%에서 틀렸습니다가 나옵니다..
시뮬레이션인데 예외가 있는지 궁금합니다..
확인하는 함수까지 첨부합니다..
#include <bits/stdc++.h>
using namespace std;
// #define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T, K, cnt;
int gears[1001];
int rotRight(int gear) {
int temp = gear & 1;
int res = (gear >> 1) | (temp << 7);
return res;
}
int rotLeft(int gear) {
int temp = gear & (1 << 7);
int res = (gear << 1) | (temp >> 7);
return res;
}
void rotate(int idx, int dir) {
int low = 1, high = T;
for (int i = idx; i > 1; i--) {
int rightGear = (gears[i] & (1 << 1)) << 4;
int LeftGear = gears[i - 1] & (1 << 5);
int dif = rightGear ^ LeftGear;
if (!dif) {
low = i;
break;
}
}
for (int i = idx; i < T; i++) {
int LeftGear = (gears[i] & (1 << 5));
int rightGear = (gears[i + 1] & (1 << 1)) << 4;
int dif = rightGear ^ LeftGear;
if (!dif) {
high = i;
break;
}
}
if (dir == 1) {
for (int i = low; i <= high; i++) {
if ((i & 1) == (idx & 1)) {
gears[i] = rotRight(gears[i]);
} else {
gears[i] = rotLeft(gears[i]);
}
}
} else if (dir == -1) {
for (int i = low; i <= high; i++) {
if ((i & 1) == (idx & 1)) {
gears[i] = rotLeft(gears[i]);
} else {
gears[i] = rotRight(gears[i]);
}
}
}
}
void printGear(int n) {
for (int i = 7; i >= 0; i--) {
cout << ((n & (1 << i)) ? 1 : 0);
}
cout << '\n';
}
void printAll() {
for (int i = 1; i <= T; i++) {
printGear(gears[i]);
}
cout << '\n';
}
int main() {
freopen("input.txt", "r", stdin);
scanf("%d", &T);
for (int i = 1; i <= T; i++) {
int gear = 0;
for (int j = 0, temp; j < 8; j++) {
gear = gear << 1;
scanf("%1d", &temp);
gear += temp;
}
gears[i] = gear;
}
// printAll();
scanf("%d", &K);
for (int i = 0, a, b; i < K; i++) {
scanf("%d %d", &a, &b);
rotate(a, b);
// printAll();
}
for (int i = 1; i <= T; i++) {
if (gears[i] & (1 << 7)) cnt++;
}
printf("%d", cnt);
return 0;
}답변 6
0
0
안녕하세요. III님 솔직히 열심히 맞왜틀 저도 찾아보고 있는데 잘 안되네요.. 제 역량부족인 것같아 죄송하다는 말씀을 드립니다. 다만 생각나는대로 틈틈히 시도해보겠습니다.
감사합니다.
0
아 드뎌 찾았습니다 반례
if (dir == 1) {
for (int i = low; i <= high; i++) {
if ((i & 1) == (idx & 1)) {
gears[i] = rotRight(gears[i]);
이거 역시 안되는 로직이네요.홀 홀
>> 시계
짝 홀
>> 반시계
짝 짝
>> 반시계 / 반례 > idx가 짝수일 때 시계방향으로 돌아야 하는데 이 때 반시계로 돌게 되네요.
홀 짝
>> 반시계
0
아 저 반례찾았어요. 아래 그림을 보면 돌리는 톱늬는 홀수이고 i가 홀수인데 오른쪽으로 회전을 안하죠? III님 같은 경우 무조건 오른쪽으로 회전한다는 로직이지 않나요?
감사합니다.
아 i가 톱니의 "개수" 가 아니고 몇번째 톱니인지 알려주는 "위치" 입니다.
그리고 idx는 돌리는 톱니의 위치구요.
그래서 i 와 idx의 짝홀이 같으면 같은 방향으로, 다르면 다른 방향으로 돌리려고 한것입니다.
예를 들어 강사님의 예시처럼 톱니가 3개가 있는데 1번 톱니를 돌린다면
1 2 3
o x o -> 1이 홀수이니 홀수인 것들은 다 같은 방향으로, 짝수인것들은 다 다른방향으로 돌아갑니다.
1 2 3 4 에서 1번을 돌린다고 하여도
o x o x -> 홀수인 것들은 o 방향, 짝수인것들은 x방향으로 돌아갑니다.
1 2 3 4 에서 2번을 돌리면
x o x o -> 마찬가지로 2와 홀짝성(?)이 같은 것들은 다 같은방향으로 돌리려고 한 로직입니다.
관련된 코드 첨부해드립니다.
dir 방향이 1일때는 idx와 홀짝성이 같은 i 번째 톱니들은 오른쪽으로 돌아가고, 홀짝성이 다른 톱니들은 왼쪽으로 돌아갑니다.
dir == -1 일때는 반대방향입니다!
혹시 로직이 잘못되었을까요? 아니면 구현이 잘못되었을까요 ㅜㅜ
if (dir == 1) {
for (int i = low; i <= high; i++) {
if ((i & 1) == (idx & 1)) {
gears[i] = rotRight(gears[i]);
} else {
gears[i] = rotLeft(gears[i]);
}
}
} else if (dir == -1) {
for (int i = low; i <= high; i++) {
if ((i & 1) == (idx & 1)) {
gears[i] = rotLeft(gears[i]);
} else {
gears[i] = rotRight(gears[i]);
}
}
}와... 말도안되네... 훌륭하네요. 정말... 아 저 성립되는 거 이해했습니다. ㄷ..ㄷ
잘 짜셨네요. 분명히 idx로부터 양옆으로 뻗어나가야 한다고 생각했는데 이게 되네요. 저부분은 틀린게 없는거 같아요.
혹시 그럼 다음 코드 설명 가능할까요?
32를 만들고, 이어서 다시 32를 만들고(있다면)
32와 32를 ^를 통해 true true면 false를 반환해서 같은 걸 반환하는 로직 맞나요?
아 틀린게 없는 거 같은데 애매하네요. 진짜.
int LeftGear = (gears[i] & (1 << 5));
int rightGear = (gears[i + 1] & (1 << 1)) << 4;
int dif = rightGear ^ LeftGear;
if (!dif) {보통은 최소 반례 체크하면 나와야 하는데...
무슨..
1
11111111
1
1 1
이런 등 등 다 해봤는데도 잘 되네요. 일단 이 문제에 붙잡히는것은 시간낭비니 내버려두시고 다른 문제 푸시고 계세요. 제가 한 일주일정도는 이 코드 시간 날때마다 틈틈히 체크해볼게요. 최선을 다해 반례를 찾아드릴게요..ㅋㅋ
감사합니다.
0
음
if ((i & 1) == (idx & 1)) {
이거 있잖아요. i가 홀수고 idx가 홀수면 right로 회전하는 건데 혹시 이게 왜 성립되는지
설명해주실 수 있을까요?다음 코드를 보시면 i가 홀수이고 idx가 홀수인 경우에 무조건 right로 돌아가는 것이 아니라 dir==1 이면 오른쪽으로 dir==-1이면 왼쪽으로 돌아갑니다
if (dir == 1) {
for (int i = low; i <= high; i++) {
if ((i & 1) == (idx & 1)) {
gears[i] = rotRight(gears[i]);
} else {
gears[i] = rotLeft(gears[i]);
}
}
} else if (dir == -1) {
for (int i = low; i <= high; i++) {
if ((i & 1) == (idx & 1)) {
gears[i] = rotLeft(gears[i]);
} else {
gears[i] = rotRight(gears[i]);
}
}
}0
안녕하세요. ㅎㅎ
일단 코드가 좀 더러운 부분이 있어서 해당 부분을 정리했고 III님 코드 기반으로 좀 다듬어봤는데요.
findL, findR 부분 등..
(gears[i + 1] & (1 << 1)) << 4; 보통은 이렇게 안 합니다. 이거 너무... 이해하기 어렵지 않나요? 해당 부분 등을 III님이 생각한 것을 유추해서 바꿔봤어요.
제 생각에는 시계방향 부분이 잘못되고 있는 것 같습니다. 참고 코드와 그림을 첨부합니다. (저의 엄청난 미술실력으로 그려봤답니다. ㅋ)
http://boj.kr/fe7a0a4df1114360adef62bebb315db0
그림까지 그려서 설명해주셔서 감사합니다!! 그런데 그림을 이해지 못했습니다 ㅜㅜㅜㅜ
그리고 첨부해주신 링크 출력초과 부분을 고치고 제출해도 답이 맞지 않습니다.
그리고 findL findR 할때 <<2 <<6 이 아니라 <<1 <<5 아닌가요??
76543210(편의상 2이상의 숫자) 이 있을 때 앞에서 부터 세번째 수인 5는 톱니의 오른쪽 바퀴를 의미하고 오른쪽에서 두번째 수인 1은 톱니의 왼쪽을 의미한다고 생각하고 풀었습니다.
그리고 low와 high를 찾고 (이것도 표현방식의 차이가 있지 로직은 맞지 않나요?)
low 부터 high까지 idx와 짝홀이 같은 것들은 해당 톱니와 같은 방향으로 움직이고, 짝홀이 다른 바퀴들은 해당 톱니와 반대방향으로 움직인다고 생각했습니다.
printAll을 이용해서 예제들을 풀어도 손으로 푼것과 같이 나오고 답을 제출해도 95%까지는 맞게 나옵니다.. 그림을 이해하지 못했고, 첨부해주신 링크로도 답을 찾을 수 없어 다시 질문드립니다.
아 1, 5가 맞습니다.
해당 부분 등을 수정한 코드는 다음과 같습니다.
http://boj.kr/d8665b172efd44bab113aad303a570f6
일단 지금까지 푼것은 이래요. III님 코드베이스로 해봤는데요. 지금 저도 예제 2까지 맞고 다른 것은 다 틀려서요. 하하...
그림은 예제 이해용으로 말씀 드린 건데 해당 부분은 이해하신 것같아 넘어가겠습니다.
전체적으로 III님 코드는 맞습니다.
다만 제 생각에 걸리는 것은 아래 부분의 코드인데요.
low 부터 high까지
if ((i & 1) == (idx & 1)) {
이게 보면 idx를 기반으로 회전등이 결정되는 건데 low부터 하는게 좀 걸려서요.
해당 부분 코드는 제가 좀 더 생각해볼게요. 반례가 있을 것 같습니다.
찾으면 여기에 다시 올려드릴게요.
감사합니다.
항상 감사드립니다 ㅜㅜㅜ