알고리즘 풀이
-
백준(BOJ) 18809번 Gaaaaaaaaaarden알고리즘 풀이/백준(Boj) 2020. 3. 28. 17:49
문제 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양 www.acmicpc.net 풀이 : loc 배열에는 0과 g에 개수만큼 1이, r에 개수만큼 2가 들어있다. 이 loc 배열을 ne..
-
백준(BOJ) 18808번 스티커 붙이기알고리즘 풀이/백준(Boj) 2020. 3. 28. 17:36
문제 : https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다. 아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다. 반면 아래는 올바 www.acmicpc.net 풀이 : 색종이는 붙일 곳이 없다고 해서 바로 return 하지 않고 일단 색종이를 붙이고 중복된 곳이 있게 된다면 다..
-
백준(BOJ) 16929번 Two Dots JAVA알고리즘 풀이/백준(Boj) java 2020. 3. 21. 18:30
문제 : https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다. www.acmicpc.net 풀이 : DFS를 통해 사이클이 발견 시 true를 반환하도록 ccheck 함수를 만들었다. 이때 by bx는 이전 y, x를 나타내는데 if (ny == by && nx == bx )는 뛰어넘도록 만들어 주었다. by와 bx가 없다면 오른쪽으로 갔다가 바로 왼쪽으로 가는 경우도 사이클로 판단하기 때문이다 코드 ( JAVA )
-
백준 BOJ(16637번) 괄호 추가하기알고리즘 풀이/백준(Boj) 2020. 3. 21. 17:06
문제 : https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다. www.acmicpc.net 풀이 : 홀수인 부분은 모두 부호이니 +면 1 *면 2 -면 3으로 바꿔서 풀어주었다. 비트 마스킹을 통해 첫 번째 예제를 예로 들면 index가 1 , 3, 5, 7, 13, 15, 17, 35, 37, 57,..
-
백준 BOJ(1445) 일요일 아침의 데이트알고리즘 풀이/백준(Boj) 2020. 3. 19. 00:45
문제: https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있다. S는 반드시 모서리에 위치해 있고, F는 모서리에 위치해있지 않다. 그리고 S와 F는 반드시 하나만 주어진다. www.acmicpc.net 풀이: 우선 주의할점은 '만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다' 이 부분이다. 칸이 비어있는 경우에만 인접한 칸에 쓰레기를 검사해야 한다. priority queue를 이용해서 { 밟은 쓰레기, 인접 쓰..
-
백준(BOJ) 알고스팟알고리즘 풀이/백준(Boj) 2020. 3. 16. 20:26
문제 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 풀이 : 우선 행 열이 아니고 열 행으로 주어지는 n, m에 주의하자. 0,0부터 시작해서 n-1 m-1로 가는 것은 priority queue를 통해서 가장 적게 벽을 부순 좌표가 먼저 나올 수 있도록 해주었다. 마이너스를 붙여서 따로 greater 처리를 하지 않고 오름차순 처리를 해주었다. 코드 ( C++ )
-
백준(BOJ) 16929번 Two Dots알고리즘 풀이/백준(Boj) 2020. 3. 13. 16:42
문제 :https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다. www.acmicpc.net 풀이 : DFS를 통해 사이클이 발견 시 true를 반환하도록 ccheck 함수를 만들었다. 이때 by bx는 이전 y,x를 나타내는데 if (ny == by && nx == bx )는 뛰어넘도록 만들어 주었다. by와 bx가 없다면 오른쪽으로 갔다가 바로 왼쪽으로 가는 경우도 사이클로 판단하기 때문이다 코드 ( C++ )
-
백준(BOJ) 16986번 인싸들의 가위바위보알고리즘 풀이/백준(Boj) 2020. 3. 13. 15:34
문제 : https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되어있기 때문에 이전 라운드의 결과와 무관하게 지우와 경희가 같은 손동작을 냈으면 경희의 승리이고, 지우와 민호가 같은 손동작을 냈으면 민호의 승리이고, 경희와 민호가 같은 손동작을 냈으면 민호의 승리이다. 비둘기집의 원리에 의해 3(K-1)+1번의 경기를 치르면 누군가 www.acmicpc.net 풀이 : 처음 p1은 0 p2는 1로 시작한다. 나머지 사람은 3 - p1 - p2로 구할 수 있다. 지수의 가위..