상근이와 정인이는 창영마을에 살고 있다. 창영마을은 전세계에서 가장 평화로운 마을로 알려져 있다. 이 마을의 이장은 상근이다.
정인이는 항상 상근이의 자리를 질투하고 있다. 정인이는 상근이가 이장의 자격이 없다는 것을 속임수를 이용해서 사람들에게 알려주려고 한다.
먼저 정인이는 불투명한 컵 세 개를 일렬로 탁자 위에 올려놓고, 가장 왼쪽 컵에 작은 공 하나를 넣어놓았다. 이제 정인이는 컵 2개를 위치를 바꿔가면서 여러 번 섞을것이고, 모두 섞은 뒤에 상근이에게 어떤 컵에 공이 들어있는지 말하라고 할 것이다. 컵이 3개가 있을 때, 위치를 바꿀 수 있는 가능한 방법은 아래와 같이 3가지가 있다.
정인이는 이날만을 위해 컵 섞기를 30년간 연습해왔다. 따라서 상근이는 아무리 쳐다보아도 정인이의 팔 속도를 따라갈수 없다.
하지만, 정인이는 상근이가 뛰어난 프로그래머라는 것을 잊고 있었다. 또한, 상근이는 정인이가 언젠간 이런 반란을 일으킬 것을 알았기 때문에, 항상 정인이와 만날 때는 모든 상황을 비디오로 녹화하고 있었다.
정인이가 컵을 섞은 방법이 순서대로 주어질 때, 어떤 컵에 공이 있는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 정인이가 컵을 섞은 순서가 주어진다. 이 순서는 A, B, C중 하나이고, 문제에 있는 그림을 참고하면 된다. 정인이는 컵을 최대 50번 섞는다.
출력
공이 가장 왼쪽 컵에 있으면 1, 중앙에 있는 컵에 있으면 2, 오른쪽에 있는 컵에 있으면 3을 출력한다.
예제 입력 1 예제 출력 1
AB 3
예제 입력 2 예제 출력 2
CBABCACCC 1
소스 코드
#include <stdio.h>
int main()
{
char a[51];
int b[3] = { 1, 2, 3 };
int c, i = 0;
scanf("%s", a);
while (1)
{
if (a[i] == 'A')
{
c = b[0];
b[0] = b[1];
b[1] = c;
}
if (a[i] == 'B')
{
c = b[1];
b[1] = b[2];
b[2] = c;
}
if (a[i] == 'C')
{
c = b[0];
b[0] = b[2];
b[2] = c;
}
if (a[i] == '\0') break;
i++;
}
for (int i = 0; i < 3; i++)
{
if (b[i] == 1)
{
printf("%d", i + 1);
}
}
return 0;
}
설명
만약 입력(a[i])에 A를 입력받았다면 1번째 컵과 2번째 컵을 바꾼다.
if (a[i] == 'A')
{
c = b[0];
b[0] = b[1];
b[1] = c;
}
만약 입력(a[i])에 B를 입력받았다면 2번째 컵과 3번째 컵을 바꾼다.
if (a[i] == 'B')
{
c = b[1];
b[1] = b[2];
b[2] = c;
}
만약 입력(a[i])에 C를 입력받았다면 1번째 컵과 3번째 컵을 바꾼다.
if (a[i] == 'C')
{
c = b[0];
b[0] = b[2];
b[2] = c;
}
만약 a배열에 맨 마지막(\0 널문자)까지 왔다면 while를 나간다.
if (a[i] == '\0') break;
맨 처음에 첫번쨰 컵에 공을 넣었으므로 1이 있는 컵을 찾아 그 컵에 위치에 따라 i + 1을 출력한다.(배열의 인덱스와 실제 순서는 1씩 차이가 있기 때문에 i를 출력하면 안되고 i + 1을 해야 됨)
for (int i = 0; i < 3; i++)
{
if (b[i] == 1)
{
printf("%d", i + 1);
}
}
Round 1B 2019 후기 간단히 올려 봅니다. 추가 설명이 필요하시면 답변 부탁드립니다~
Round 2로 진출한 상황이어서 시험 종료 후에 풀어봤습니다.
문제는 세 문제였습니다.
ㅁ 1번 Test Set1 (Manhattan Crepe Cart) 각각의 사람에 대해서 지나가는 위치를 +1증가 시키면 됩니다. 시간 복잡도는 O(P*Q*Q)이고, P=500, Q=10이라서 제한 시간안에 실행이 가능합니다.
ㅁ 1번 Test Set2 Q=100000이기 때문에 위의 방법으로는 TLE(Time Limit Expire)가 발생하기 때문에 더 좋은 방법이 필요합니다. X좌표와 Y좌표를 따로 생각해도 된다는 게 문제의 핵심입니다. 현재 좌표가 (x1,y1)일 경우, 북쪽 방향은 Y [y1+1].. Y [Q]까지 1을 더하고 남쪽 방향은 Y [y1-1].. Y [0]까지 1을 더하고 동쪽 방향은 X[x1+1]..X[Q]까지 1을 더하고 서쪽 방향은 X [x1-1].. X [0]까지 1을 더하면 됩니다.(DP로 O(1)으로 연산 가능)
X배열에서 최소인 x좌표(같을 경우 작은값)와 Y배열에서 최소인 y좌표(같을 경우 작은 값)가 답이 됩니다. 시간 복잡도는 O(Q) 입니다.
2번은 제가 어려워 하는 Interactive problem이었습니다. ㅁ 2번 Test Set1 (Draupnir) D0, D1, D2, D3, D4, D5를 질문하면 풀 수 있습니다. D1-D0=R1, D2-D1=R2, D3-D2=R3, D4-D3=R4, D5-D4=R5, D0=R6를 구할 수 있습니다.ㅁ
2번 Test Set2 Ri 최댓값이 100(7bit)인 점과(property-1), 2^63으로 modular 한다는 점을(property-2) 이용해야 합니다. property-1: y = Ri * 2^i + Rj * 2^j 에서 abs(i-j)>=7인 경우 y, i, j값을 이용해서 Ri, Rj를 구할 수 있습니다. property-2: y = Ri * 2^i + Rj * 2^j 에서 i>=63일 경우 (Ri * 2^i) % 2^63은 0이 됩니다. y = R1*2^x1 + R2*2^x2 + R3*2^x3 + R4*2^x4 + R5*2^x5 + R6*2^x6 일 경우, property-2를 통해서 R1*2^x1=R2*2^x2=R3*2^x3=0이고(x1,x2,x3>=63), x4/x5/x6의 차이가 7 이상인 Day를 질문하면 R4/R5/R6를 구할 수 있습니다. 이런다음에 x1, x2, x3의 차이가 7 이상인 또 다른 Day를 질문하면 R1/R2/R3를 구할 수 있습니다.(R4/R5/R6는 이미 알고 있음)
ㅁ 3번 Test Set1 (Fair Fight) 모든 L,R(1 ≤ L ≤ R ≤ N)에 대해서 C, D에서 최댓값을 찾은 후에 각각의 최댓값의 차이가 K이하인 경우를 count 하면 된다 시간 복잡도는 O(N^3)이고 N=100이기 때문에 시간 내에 수행 가능 하다