본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[boj] 백준 gold5 5557 1학년 (Java) - dp [문제] https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net [풀이] dfs로 풀게 되면 O(2^n)의 시간복잡도를 갖게 된다. dp를 통해 해결할 수 있는데 이전의 수에 현재 수를 +하거나 - 하는 2가지 경우가 존재한다. 또한 수가 0~20 사이에 존재해야 한다. 따라서 dp[i][num] 은 0~i 번까지의 수를 차례로 더하거나 빼서 num을 만들 수 있는 경우의 수로 두고 풀 수 있다. [코드] package dp; import ja..
[boj] 백준 21611 마법사 상어와 블리자드 (Java) - 시뮬레이션 [문제] [풀이] 오늘 하루종일 마법사 상어와 복제 디버깅만 하다가 끝나는 줄.. (어디서 막혔는지 알고 신나서 고쳐서 예제 다 돌아가길래 맘편히 자나 했는데 시간초과 떠서 던짐) 이 문제의 키포인트는 1~n*n-1 까지의 달팽이 수열에 대해 미리 r, c 좌표를 저장해두고 사용하면 된다는 거다. 이 수열은 마법사 상어와 토네이도 문제에서 나온 것과 똑같이 구현해줬다. 1. di, si 방향으로 얼음을 날려서 구슬을 파괴한다. 이때 파괴된 구슬은 폭발한 구슬이 아니라 세면 안된다. 2. 구슬이 빈칸을 채우기 위해 이동한다. 3. 4개 이상 연속하는 구슬이 폭발한다. 4. 다시 구슬이 빈칸을 채우기 위해 이동한다. 더이상 폭발하는 구슬이 없을 때까지 2-3을 반복한다. 5. 구슬이 변화한다. 연속하는 구슬..
[boj] 백준 20055 컨베이어 벨트 위의 로봇 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net [풀이] 단순 시뮬레이션. 하라는 순서대로 구현하면 된다. 딱히 설명할 게 없다.. 편의를 위해 컨베이어 벨트 내구도를 저장하는 배열과 로봇 위치를 저장하는 배열을 따로 뒀는데 컨베이어 벨트 회전할 때 로봇 위치도 변경하는 거 잊지 않도록 주의! [코드] package 시뮬레이션; import java.io.*; import java.util.*; public cla..
[boj] 백준 21068 상어 초등학교 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net [풀이] 1. 자리를 배치하는 번호 순대로 앉을 수 있는 모든 자리를 넣는다. 정렬에 필요한 요소인 인접 칸에 앉은 좋아하는 학생 수, 인접 칸에 비어있는 자리수를 자리의 행, 열 번호와 함께 저장해주었다. 2. 조건에 맞게 정렬한 후 학생을 자리에 앉힌다. 3. 학생들이 모두 자리에 앉으면 만족도 합을 구한다. [코드] package 시뮬레이션; import java.util..
[boj] 백준 21609 상어 중학교 (Java) - 시뮬레이션, BFS [문제] https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net [풀이] 1. 블록 그룹을 구한다. 인접해있고, 같은 색의 일반 블록과 무지개 블록으로 구성되어있으며 검은 블록은 포함되면 안된다. BFS를 돌려서 구할 수 있다. 정렬에 필요한 데이터들을 저장해주었다. 중요한 점은 무지개 블록은 중복되어 포함될 수 있다!! 대놓고 써져있지 않아서 처음에 이 부분을 간과했는데 "무지개 블록은 얼마나 들어있든 상관없다." 는 부분을 주의해야 한다. 이를..
[boj] 백준 23288 주사위 굴리기 2 (Java) - 시뮬레이션, BFS [문제] https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net [풀이] 1. 주사위를 굴린다. 이 문제의 핵심 부분이다. 주사위를 어떻게 굴릴지 고민하다가 전개도를 가로, 세로 나눠서 두가지 배열로 저장했다. 동쪽으로 굴리면 가로배열이 한칸씩 오른쪽으로 이동하고, 서쪽으로 굴리면 가로배열이 한칸씩 왼쪽으로 이동한다. 남쪽으로 굴리면 세로배열이 한칸씩 오른쪽으로 이동하고, 북쪽으로 굴리면 세로배열이 한칸씩 왼쪽으로 이동한다. 이때 가..
[boj] 백준 21610 마법사 상어와 비바라기 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net [풀이] 마법사 상어와 파이어볼 문제와 상당히 유사하다. 1. 초기 구름은 (N, 1), (N, 2), (N-1, 1), (N-1, 2) 에 존재한다. 구름 리스트를 만들어 구름을 세팅한다. 2. d방향으로 s만큼 구름을 이동한다. 이때 주의해야 할 점은 1-N 열과 행이 연결되어 있기 때문에 인덱스 오류가 나지 않도록 설정해야 한다. 위 문제와 똑같은데, d[i]*s%n 만큼 이..
[boj] 백준 20058 마법사 상어와 파이어스톰 (Java) - 시뮬레이션(배열 회전), BFS [문제] https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net [풀이] 1. 2^L x 2^L 의 부분격자를 시계방향으로 90도 회전시킨다. 2. 3면 이상 얼음에 닿아있지 않으면 얼음의 양이 1 줄어든다. 3. 남아있는 얼음의 양의 합과 가장 큰 덩어리의 칸의 개수를 출력한다. 2^L x 2^L 의 부분격자에 대해 2차원 배열 회전을 시켜줘야 한다. 2차원 배열 회전은 직접 그림을 그려서 어떻게 회전이 되는지 확인했다. 1 2 ..

티스토리툴바