코딩하기 좋은날

https://www.acmicpc.net/problem/14503 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 로봇 청소기가 청소를 할때 몇칸을 청소 하는지를 구하는 문제입니다. 기본적으로 로봇 청소기가 바라보는 방향이 주어지고 로봇 청소기는 그방향을 기준으로 왼쪽으로 방향을 회전하면서 청소를 할 수 있을때 전진하여 청소를 합니다. 청소를 하지 못할경우 뒤가 벽이 아니라면 후진을 하며 계속해서 진행을 하고 후진을 못하면 정지하게 되는 원리로 작동합니다. 따라서 입력받은 기준으로 왼쪽으로 회전시키는 좌표 배열과, 후진할때 좌표를 조절하는 배열을 따로 만들어서 탐색을 해주어야 합니다. 방향이 0부터 시작해서 북 동 남 서 이므로 왼쪽으로 회전하는 것은 인덱스에서 -1씩 가는 것과 동일합..

https://www.acmicpc.net/problem/14502 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 연구소에 벽이 있고 바이러스들이 존재할때 바이러스가 상하좌우로 퍼져 나갑니다. 이때 벽을 3개를 추가 시킬 수 있는데 바이러스가 퍼지지 않는 영역의 최대를 구하는 문제입니다. 연구소 크기가 최고 8*8이므로 그냥 벽이 없는 곳중에 3곳을 찾아 벽을 세우고 그 배열을 대상으로 bfs를 해서 안전영역을 구하면 되는 문제입니다. 재귀 함수를 통해 벽 3개를 추가 시켜주고 거기서 bfs를 통해 바이러스를 퍼트려 주면 됩니다. 다음은 코드입니다. #include #include using namespace std; int arr[8][8]; queue q; int N,M; int nextx[4..

https://www.acmicpc.net/problem/13460 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 삼성 역량 테스트 기출문제를 풀려고 들어갔다가 맨 위에 있어서 풀었는데 생각보다 까다로운 문제였습니다 ㅠ ㅠ 빨간 구슬과 파란 구슬이 있는데 이 구슬들을 상하 좌우로 기울여서 구멍에 넣어야 하는데 이때 기울이는 최소의 회수를 구해야 합니다. 그러나 파란 구슬이 먼저 빠지거나, 동시에 빠지는 경우는 포함하지 않아야 합니다. 일단은 코드가 깁니다. 짧게 짜신 분들도 있으신거 같은데 이런저런 조건을 자꾸 넣다보니 코드가 길어졌습니다. 우선은 구슬이 2개이므로 2개다 움직이는 것을 생각해 주어야합니다. 저는 이 구슬들의 방문점을 체크하기 위해 4차원 배열을 잡았습니다. 그래서 빨간 구슬과 파..

https://www.acmicpc.net/problem/2263 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 트리의 중위 순회 순서와 후위 순회 순서를 입력받아 전위 순회 순서를 출력하는 문제입니다. 중위 순회와 후위 순회를 예를 만들어서 보게되면 후위 순회의 가장 끝이 항상 root를 나타냄을 알 수 있고 중위 순회에서는 그 루트를 기준으로 왼쪽에 있는 값들이 왼쪽 자식들이고 오른쪽에 있는 값들이 오른쪽 자식임을 알 수 있습니다. 따라서 이 특성을 이용하여 분할 정복을 통해 문제를 풀어야 합니다. 헷갈려서 쉽지 않은 문제였습니다,, 다음은 코드입니다. #include using namespace std; int in[200000]; int post[200000]; int n; vo..

https://www.acmicpc.net/problem/3163 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 막대에 개미가 있을 때 개미들이 떨어지는 순서를 구하는 문제입니다. 각 개미들은 이동 방향이 있고 충돌할 경우 방향이 바뀌게 되는데 이문제 같은 경우 충돌을 굳이 고려하지 않아도 되는데 그 이유는 왼쪽과 오른쪽으로 개미들이 떨어질 때 처음의 아이디 순서대로 반드시 떨어지기 때문입니다. 따라서 처음 위치를 입력받은 뒤 방향에 따라 떨어질 때까지 거리를 계산해서 절대값 순서로 정렬을 하였습니다. 그런다음 K번째 떨어지는 개미를 구하면 되는데 이 때 개미가 동시에 떨어 질때는 id가 작은 개미가 먼저 떨어지므로 절대값이 동일한 경우 두 id를 비교해서 swap을 해준 뒤 최종적으로..

https://www.acmicpc.net/problem/1074 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 크기가 2*2 일때 Z모양으로 각 원소를 탐색하는 배열이 있을 때 주어진 크기의 배열에서 r,c에 해당하는 원소를 몇번째로 방문하는지 구하는 문제입니다. 배열의 크기는 2^N * 2^N 이므로 한번 쪼개질때 4등분이 나고 총 배열의 크기는 N이 15까지 가능하므로 32768*32768의 어마어마한 크기가 됩니다. 따라서 배열을 정의해서 풀 수는 없고 저는 r,c가 존재하는 범위의 구역까지 쪼개면서 그이전에 방문지점들을 더해주는 방식으로 풀었습니다. 예를들어 4*4 배열이 있을때 제일 끝점인 15,15 에 원소가 존재한다면 처음에 2*2 4개로 쪼개지고 가장 오른쪽 아래에 있는 ..

https://www.acmicpc.net/problem/1934 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 두수의 최소공배수를 구하여 출력하는 문제입니다. 10과 50의 최소공배수는 50입니다. 이때 이것을 구하는 방법은 10과 50의 최대공약수인 10을 각숫자에 나눈몫들과 곱하면 됩니다. 즉 10(gcd) * (10/10) * (50/10) 을 해주면 최소공배수를 구할 수 있습니다. 따라서 유클리드 호제법을 이용하여 gcd를 구하고 그것을 이용하여 최소공배수를 구하면 됩니다. #include using namespace std; //최대공약수를 구해서 최대공약수를 이용해 최소공배수를 구함 int gcd(int a, int b) { if(b == 0) return a; return ..

https://www.acmicpc.net/problem/9461 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 삼각형이 나선형으로 놓여집니다. 이때 나선에서 가장 긴변의 길이를 k라고 하고 k길이의 정삼각형을 추가하는 방식으로 배치가 되는데 N번째 진행시 k의 값을 구하는 문제입니다. 수열을 쭉 보시면 1 1 1 2 2 3 4 5 7 9 12 ... 으로 진행되는데 n번째 값은 n-1과 n-5를 더하면 나온다는 것을 알 수 있습니다. 따라서 그에따라 점화식을 세워주면 풀리는 문제입니다. 주의할점은 n이 100까지 가능하므로 오버플로우가 일어날 수 있어 longlong형으로 선언 해주셔야 합니다. 다음은 코드입니다. #include using namespace std; int main(v..