데구리 블로그

문제 링크 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개의 표본 모양수열이 같은 다각형을 그리게 됩니다. 여기에 역방향으로 돌리는 경우까지 생각해줍시다 예제의 표본 모양..

문제 링크 www.acmicpc.net/problem/2650 2650번: 교차점개수 입력의 첫째 줄에는 주어진 점들의 개수가 있다. 단, 점들의 개수는 50을 넘지 않는다. 둘째 줄 이후부터는 각 줄에 모양이 같은 두 점의 위치가 네 개의 숫자로 주어지는데, 첫 번째와 두 번째 숫 www.acmicpc.net 풀이 세 직선이 한 점에서 교차하면 안되고, 원하는대로 곡선을 그릴 수 있습니다. 항상 하나의 교차점에서 두 선만 교차하므로 모든 선에 대해 $O(N^2)$으로 교차 여부를 판별하면 됩니다. 문제에서는 직사각형을 줬는데, 이를 원으로 생각하면 쉽게 풀 수 있습니다. 모든 점을 적당한 연산을 통해 원 위의 한 점으로 바꿔주고, 선을 이루는 두 점을 페어로 저장합니다. 이때 항상 좌표가 작은 점이 앞..

문제 링크 www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 풀이 가능한 모든 네 자리 수의 조합을 찾고, 4번씩 돌려서 시계수를 찾은 다음 중복을 제거해줍니다. 입력으로 들어온 시계수가 몇 번째로 작은 수인지 lower bound를 이용해 구해주면 됩니다. 정답 코드 #include #define all(x) (x).begin(), (x).end() using namespace std; vector p; int main() { int a, b, c, d; cin >> a >> b >>..

문제 링크 www.acmicpc.net/problem/2658 2658번: 직각이등변삼각형찾기 입력된 모양이 직각이등변 삼각형을 이루는 경우에는 세 꼭짓점의 위치를 출력하고, 그렇지 않은 경우에는 0을 출력한다. 각 꼭짓점의 위치를 한 줄에 두 개의 수로 출력한다. 두 수는 하나의 빈 www.acmicpc.net 풀이 가능한 모든 경우의 삼각형을 다 그려보고 입력과 같은지 비교해봅시다. 오랜만에 별 찍기 하는 느낌이 들었습니다. 가능한 모든 삼각형은 다음과 같습니다. 순서대로 go0, go1, ..., go7이며 아래 네 개의 삼각형은 위 네 개 삼각형의 조합으로 그릴 수 있습니다. 정답 코드 #include #define ft first #define sd second using namespace st..

문제 링크 programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 풀이 가로, 세로가 주어지고 격자점을 관통하는 직선이 보입니다. 이건 누가 봐도 소인수 관련 문제입니다. 최대 공약수로 몇 번 끄적여서 규칙을 찾았습니다. 정답 코드 const gcd = (a, b) => b===0 ? a : gcd(b, a%b); function solution(w, h) { const g = gcd(w, h); con..