문제
로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다. 세희의 목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다. 아래의 예시를 참고하자.
초기 상태목표 상태| ○●●○○ | ○●○●○ |
세희는 로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다.
- 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
- 말 1개를 들어 뒤집어 놓아 색상을 변경한다.
위의 예시에서, 3번째와 4번째 말을 2번 작업을 통해 각각 뒤집으면 2번의 작업으로 목표 상태를 만들 수 있다. 하지만 1번 작업을 통해 3번째와 4번째 말을 골라 서로의 위치를 바꾸어주면 1번 만에 목표 상태에 도달할 수 있다. 초기 상태의 말과 목표 상태의 말이 주어질 때, 목표 상태에 도달할 수 있는 최소 횟수를 구하는 프로그램을 작성하시오.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 각 입력의 첫 번째 줄에는 오셀로 말의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 각 입력의 두 번째 줄과 세 번째 줄에는 각각 오셀로 말의 초기 상태와 목표 상태가 주어진다. 초기 상태와 목표 상태의 말의 개수는 항상 N과 일치한다. 흰색 면이 보이는 경우에는 W, 검은색 면이 보이는 경우에는 B로 주어진다.
출력
출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 한 줄에 1개씩 초기 상태에서 목표 상태를 만들기 위한 작업의 최소 횟수를 구한다.
그리디 알고리즘은 욕심꾸러기 알고리즘입니다.
처음부터 끝까지 정답을 찾기 위해서 전부 탐색하는 알고리즘이며, 작성은 간단하지만 효율성이 최악인 알고리즘이기도 합니다. 이러한 알고리즘은 자료구조를 사용하지 않는 간단한 기능에서는 널리 사용되지만 대규모의 데이터를 처리해야되는 상황에서 이러한 방식을 이용하는 것은 선배들한테 혼날 수 있습니다! 조심하세요!
하지만 본 문제는 그리드 알고리즘에 대해서 알고 있는지 있는 묻는 문제이기 때문에
저는 아래와 같은 코드를 작성하여 문제를 풀었습니다.
5년전에 작성했던 문제 풀이코드는 C언어로 작성되었으며,
if문에 중괄호가 없는 것을보니 가독성 따위는 포기하며 작성을 한 것 같습니다.
현업에서 이렇게 작성하면 한소리 들을 수 있으니 주의하시기 바랍니다!
#include<stdio.h>
#include<string.h>
int main(){
char a[100001];
char b[100001];
int test;
scanf("%d",&test);
while(test--){
int len;
scanf("%d",&len);
scanf("%s %s",&a,&b);
int wb = 0,bw = 0;
int ct = 0;
for(int i = 0 ; i < len ; i++){
if(a[i] != b[i]){
if(a[i] == 'W')
wb++;
else if(a[i] == 'B')
bw++;
}
}
while(wb && bw){
wb--;
bw--;
ct++;
}
printf("%d\n",wb+ct+bw);
}
}이상 다이어릿이었습니다!
감사합니다.
