2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 다리를 놓아 모든 섬을 연결할 수 있을 때, 다리 길이의 합의 최솟값을 찾는 문제이다. 다리는 1️⃣ 섬끼리 인접한 바다에서만 직선으로 설치할 수 있다 2️⃣ 중간에 방향전환을 할 수 없다 3️⃣ 길이는 2 이상이다 라는 조건을 가지고 있다 위의 그림에서, 초록색으로 칠해진 부분이 다리를 설치할 수 있는 부분이다. 그래서 각각의 구역에서 BFS를 돌려 섬 번호를 나누고, 섬 ..

https://www.acmicpc.net/problem/15953 15953번: 상금 헌터 첫 번째 줄에 제이지가 상상력을 발휘하여 가정한 횟수 T(1 ≤ T ≤ 1,000)가 주어진다. 다음 T개 줄에는 한 줄에 하나씩 제이지가 해본 가정에 대한 정보가 주어진다. 각 줄에는 두 개의 음이 아닌 정수 a(0 ≤ a ≤ 100)와 b(0 ≤ b ≤ 64)가 공백 하나를 사이로 두고 주어진다. www.acmicpc.net 단순 구현 문제(난이도 하)지만 신경써서 풀지 않으면 나처럼 5번씩 틀리게 된다 ^^ 풀이 방법은 입력을 받기 전 제1회 -> 1등 1명, 2등 2명, 3등 3명, ... 을 배열에 넣어준다 [1,2,2,3,3,3,4,4,4,4, ...] 제2회 -> 1등 1명, 2등 2명, 3등 4명,..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 할만한가?싶다가도 ㅇㅏ닌 악마같은 문제.... 😠 어찌보면 삼성 역량테스트의 표준같은 문제였당 나는 두 가지 방법으로 문제를 풀었다 ① 일단 역테 기출중에서 많이 쓰는, 모든 경우 완전탐색을 위해 DFS로 방향 경우의 수를 구한 뒤 방향 순서에 따라 5번 이동을 해주고 배열 최댓..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 엄청나게.... 빡취는 문제 구슬이 들어있는 판을 이리저리 굴려서(이동이 멈출때까지 방향 전환X) 10회 안에 구멍에 빨간 구슬..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net ^- 문제링크 인구 이동 문제는 맞닿아있는 국가와의 인구 수 차이가 L이상 R 이하일 경우 국경을 열어 열린 국가들끼리 인구 수를 평..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net ^- 문제링크 테트리스 블록을 회전/대칭했을 때의 모양을 고려하여 배열에 덮었을 때 덮은 숫자의 최댓값!을 찾는 문제이다 ㅇㅖ를 들..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 완전탐색으로 그래프를 두 구로 나누어 각각 연결요소의 개수를 구하고, 2개일 경우에만 차이의 최솟값을 구하는 문제 크게 세 부분으로 나뉜다. 1. N개의 구를 두 진영으로 나누는 경우의 수 구하기 2. 각각의 요소들을 BFS로 연결요소가 두 개인지 구하기 3. 두 연결요소의 차의 최솟값 구하기 일단 1. 백트래킹을 이용해서 depth가 N일 때 까지 콜스택을 쌓고 2. 1번 요소에서 BFS를 돌려서 전부 visit됐다..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐 www.acmicpc.net 캐슬 디펜스와 같이 A형 기출문제였던 색종이 붙이기 문제!! 처음에는 그냥 로직을 맵을 돌면서 가장 큰 색종이부터 작아지는 순서대로 붙이는 그리디한 방..