문제 링크 www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 치즈 외부의 공기와 접촉하면 치즈가 녹아 없어지지만, 내부 공기와 접촉된 치즈에 대해선 처리하지 않아야합니다. bfs를 돌리는데, 치즈를 주체로 돌리지 않고 (0, 0)의 공기를 시작점으로 하여 돌려줍시다. 정답 코드 #include #define ft first #define sd second using namespace std; using pii = pair; int n, m; int p[111][111]; b..
문제 링크 www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 단순 시뮬레이션 문제입니다. 들어온 입력에 따라 문제에서 요구하는대로 구현하면 됩니다 스위치를 켜고, 끄는 연산은 1과 XOR해주면 쉽게 처리됩니다. 정답 코드 #include using namespace std; int n, m; int p[111]; int main() { cin >> n; for (int i = 1; i > p[i]; } cin >..
문제 링크 www.acmicpc.net/problem/2635 2635번: 수 이어가기 첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다. www.acmicpc.net 풀이 규칙이 주어집니다. 그에 따라 구현을 합시다. 두 번째 수로 $N$ 이상의 수를 선택하면 항상 바로 끝나게 되니 $N$ 이하의 모든 수에 대해 돌리면 됩니다. 정답 코드 #include #define ft first #define sd second #define INF 0x3f3f3f3f using namespace std; using vi = vector; int go(vi &p) { int top = (int) p.size() - 1; if (p.back() < 0) { p.pop_back(); ret..
문제 링크 www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net 풀이 1) 색종이의 두 변 중 작은 변이 항상 앞으로 오도록 저장하고, 오름차순 정렬해줍니다. 2) 배열 $d$를 정의합시다. $d[i]$는 $i$번째 색종이보다 작거나 같은 색종이들을 $i$번째 색종이 위에 최대로 쌓을 수 있는 개수입니다. 3) 가장 긴 증가하는 부분 수열 (LIS) 문제와 같은 방식으로 $d[i]$를 갱신할 수 있습니다. 4) 모든 $d[i]$ 중 가장 큰 값을 정..
문제 링크 www.acmicpc.net/problem/2642 2642번: 전개도 입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나 www.acmicpc.net 풀이 실제로 정육면체를 굴려주는 구현을 하면 됩니다. 전개도를 탐색하며 처음 만나는 면을 밑면으로 잡고, dfs로 탐색하며 큐브를 굴려줍시다. 정육면체를 만들 수 없는 경우는 다음과 같습니다. 1) 입력받은 전개도에서 0이 아닌 수가 6개가 아님 2) dfs가 끝난 후 큐브의 6개 면이 다 채워지지 않음 정답 코드 #include #define ft first #define sd second using..
문제 링크 www.acmicpc.net/problem/2641 2641번: 다각형그리기 모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 www.acmicpc.net 풀이 주어진 표본 모양 수열의 어디서 시작하든, 그 길이만큼만 똑같이 돌려주면 같은 모양의 다각형을 만들 수 있습니다. 문제 예제의 1411433322을 예로 들어봅시다. 1411433322 4114333221 1143332214 1433322141 ... 2141143332 이렇게 10개의 표본 모양수열이 같은 다각형을 그리게 됩니다. 여기에 역방향으로 돌리는 경우까지 생각해줍시다 예제의 표본 모양..