runBOJ그룹-ps1주차

현재 포스트의 문제집

정수 직사각형 (문제)

---

문제 조건

시간제한 1초, 메모리제한 128MB, $0 < h, w \le 100$, $tc < 100$

tc = 테스트 케이스

문제 설명

주어진 넓은 정수 직사각형보다 큰 넓은 정수 직사각형 중 가장 작은 것을 찾는 문제
(=> 다음으로 큰 정수 직사각형을 찾는 문제)

정수 직사각형의 크기는 아래의 규칙에 의해 정해진다.

1. 대각선의 길이가 짧은 쪽이 작다.
2. 대각선의 길이가 같은 경우에는 높이가 작은 것이 작다.

w > h인 직사각형을 넓은 직사각형이라고 한다.

풀이

시간복잡도가 $h * w * tc$여도 충분히 풀 수 있음(1,000,000)

w > h

1. $w^2 + h^2$를 비교해서 더 크면 큰 직사각형
2. $h$를 비교해서 더 크면 큰 직사각형

위 3가지 조건을 이용해서 풀면 된다.

문제 해결 방법

1. 대각선의 길이가 같고, 높이가 더 높은 직사각형을 찾는다.
2. 대각선의 길이가 더 긴 직사각형을 찾는다.

(아래와 같은 내용)

1. 같은 $w^2+h^2$값을 가지고, $h$가 더 큰 직사각형을 찾는다.
2. $w^2+h^2$에 1씩 더한 값을 가지는 직사각형을 찾는다.

$w^2+h^2$를 가지는 직사각형을 찾는 방법
높이(r)를 1에서 h까지 증가시키고, $w^2+h^2 - r^2$이 어떤 수(j)의 제곱일때,
r은 높이(h), j는 폭(w)이 된다.

해결 코드(pypy3)

톱니바퀴 (문제)

---

풀이

시간제한도 넉넉하고 메모리제한도 넉넉해서 보니 구현문제같다.
구현문제는 딱히 설명할게 없으니 바로 바로 풀이로 진행하겠다.

톱니바퀴를 돌렸을때의 상태와 돌리기 전의 상태를 저장한다.
돌리기 전의 상태를 보고, 서로 극이 다르면 회전시킨다.
회전을 시킬때는 가장 처음 돌리는 톱니바퀴를 기준으로 좌측, 우측으로 나누어 진행한다.
3번이 돌아가면 2->1 순으로 좌측 톱니를 확인하고, 우측 톱니인 4번을 확인하면 된다.

주의할 점은 입력순서대로 입력을 받았을때, 톱니의 8방향중에서 위는 gear[0], 오른쪽은 gear[2], 왼쪽은 gear[6]이 된다.

정리하면,

1. 첫 회전 톱니를 기준으로, 좌측에 있는 톱니들을 돌린다.
2. 첫 회전 톱니를 기준으로, 우측에 있는 톱니들을 돌린다.

톱니 회전(좌측 기준, 오른쪽은 방향 반대로)

1. 이전 톱니의 왼쪽 이빨과, 현재 톱니의 오른쪽 이빨의 극성을 비교해서, 다르면 회전시키고, 다음 톱니도 같은 방식으로 진행한다.

해결 코드(pypy3)

Baaaaaaaaaaaaaaaaaaaaaaaaaaduk2(easy)

---

문제 조건

시간제한 2초, 메모리제한 512MB, $(3 \le N, M \le 20)$

풀이

2초에 512MB, 게다가 보드의 크기는 커봐야 2020
보드에 놓아야 할 돌은 2개, 나올 수 있는 위치의 조합은 최대 ${2020 \choose 2} = 79,800$, 400개의 정점을 가진 보드, bfs해도 되겠다.

(i, j)위치에 돌을 놓고, (i, j)다음으로 올 수 있는 위치에 돌을 놓고 bfs를 통해 각 돌의 상하좌우를 탐색하여 딸 수 있는 돌의 수를 구하고, 이 값을 기존 최대값과 비교하여 구할 수 있다.

1. (i, j), (k, l)위치에 돌을 놓는다.
2. 놓은 두 돌의 상하좌우를 탐색하여 따낼 수 있는 돌의 수를 구한다.
3. 따낼 수 있는 돌의 최대값을 업데이트 한다.

bfs할때는 탐색도중 빈 공간을 발견하면 종료하도록 했다. (i,j)은 왼쪽 위부터 지정하도록 했고, (k,l)은 (i,j) 다음으로 올 수 있는 위치부터 지정하도록 했다.

해결 코드(pypy3)

직사각형으로 나누기

---

문제 조건

$(0 < N, M \le 100, 3 \le N*M)$
시간제한 2초, 메모리제한 128MB

풀이

위 사진과 같이 나눌 수 있다.

왼쪽 4가지 경우는 가로줄 세로줄 기준으로 해결하면 된다. 세로줄(|)을 i의 위치, 가로줄을 j의 위치에 놓고 왼쪽 위 오른쪽 위 왼쪽 아래 오른쪽 아래를 나누고, 왼쪽이 긴경우 위쪽이 긴경우 오른쪽이 긴 경우 아래쪽이 긴 경우를 나누어 왼쪽 케이스를 해결했다.

그림처럼 나누는 것을 구현하면 된다.

해결 코드(c++17)

오목

풀이

입력을 모두 받고 보드의 모든 부분에서 탐색해서 오목이 완성됬는지 확인한다.
단, 육목 이상은 성립하지 않으니 이 부분도 참고해서 구현해야한다.
(육목이상 조건 안보고 3번인가 틀림)

해결코드(c++17)

차트(https://www.acmicpc.net/problem/1239)

풀이

0에서 101까지 나누고, bool값을 이용해서 선의 유무를 표시했다.
next_permutation을 이용해서 모든 순열을 만들어서 구했다.
이를 이용해서 구해진 순서대로 차트를 구성하면서 선의 유무를 체크하고, 50이 넘는 경우 선이 이어지는지 확인했다.

해결코드(c++17)

배열돌리기

풀이

차트 문제랑 같다.
next_permutation으로 회전의 순서를 나타내는 순열을 구하고, 그 순서에 맞춰서 회전시키고, 회전을 했을 때의 배열의 값을 구해서 최대값을 구했다.

해결코드 (c++17)