본문 바로가기
    <

Algorithm/Baekjoon12

[백준] 1188번 음식평론가 (Java) / 유클리드 호제법 📍 문제 링크 https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 📍 문제 접근 소세지 수와 평론가 수 사이의 최대공약수 관련 문제인 느낌은 있었지만, 정확한 방법이 생각나지 않아 구글링을 했다. 대부분의 블로그에서 "평론가 수 - gcd(소세지수, 평론가수)" 가 답이라는 것을 보았고, 해당 식이 나온 이유를 고민해보았다. 소세지 수: n개, 평론가 수 m: 명이라고 하자. 소세지를 1개로 이어붙혔을 때, m조각이 나오려면 m-1번 칼질을 하면 된다. 이 때, n과 m이 서로소인지 확인이 필요하다. 1) n과 m이 서로소인 경우 아래 그림처럼 소세지.. 2023. 4. 25.
[백준/Java] 11559 PuyoPuyo / 구현, BFS 📍 문제 링크 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 📍 문제 접근 전형적인 구현 문제이다. 문제의 과정대로 단계를 나누어 구현했다. 아래의 단계를 가능할 때까지 반복하면 된다. 1. 터뜨릴 뿌요 블록 구하기(+ 터뜨리기) 2. 뿌요 블럭 내리기 1. 터뜨릴 뿌요 구하기 (bfs) static boolean popPuyo(int r, int c) { int count = 1; // 뿌요 그룹에 들어가는 블럭 수.. 2023. 2. 27.
[백준] 1010번: 다리놓기-(Java) /수학, DP 📍 문제 링크 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 순서가 없다. 1, 2 규칙에 의해 다리를 짓는 개수는 동쪽의 사이트 m개 중 n개를 뽑는 조합의 공식이라는 것을 알 수 있다. 이용한 조합 공식은 다음과 같다. 공통으로 메모.. 2022. 6. 3.
[백준] 1041번: 주사위-(Java) / 그리디 📍 문제 링크 https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 📍 문제 접근 1. 우선 크기가 N*N*N 인 정육면체를 직접 그려보면서 각 주사위의 눈에 보이는 면에 대한 규칙을 찾았다. 주사위의 눈에 보이는 면의 수는 3개, 2개, 1개의 면이 보이는 경우로 총 3가지이며, 개수는 다음과 같다. ex) N= 3 인 경우 면의 수가 3개인 경우는 아래의 그림과 같이 윗면의 양 모서리에 있는 주사위로 총 4개이다. 면의 수.. 2022. 5. 13.