내맘대로블로그

www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net Gold 4 횟수 갯수 만큼의 단계가 주어지면 그 단계(= 칸수)를 기준으로 회전하고 얼음을 녹인다. 1. 2^n만큼 구역을 나눠주고 그 칸을 회전한다. 2. 전체 탐색하며 얼음을 녹여준다. 3. 1,2를 주어진 단계만큼 수행한다. 4. 제일 큰 덩어리와 얼음의 합을 출력한다. -> 나의 경우엔 회전과 얼음을 녹이는 부분에서 시간이 많이 걸렸다. [회전 부분] public static int..

www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net Gold 5 완전 탐색! DFS도 되고 BFS도 되지만 난 BFS로 풀이! 1. 완전 탐색(for 문 2번 돌리기)로 동서남북을 확인하며 범위내에 해당하는지 확인 1) 해당하면 queue에 넣어서 인구 이동이 가능한지를 탐색(BFS나 DFS사용) 가능하다면 flag를 둬서 가능함을 표시(나중에 인구 이동 발생 횟수를 증가 시키기 위함) 2) 이동 가능한 인구 수 의 합계를 구하기 위해 변수를 정하..

www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net Gold 5 나의 경우엔 안 되는 상점의 조합을 구해서 풀었다. 안 되는 상점의 조합은 DFS, 백트래킹이용 상점을 이용한 최단 거리는 BFS를 풀려고 했지만 시간 초과가 나왔다. 그래서 DFS + 완전 탐색로 풀었더니 정답! 거리 구하는 부분에서 헤매지만 않았으면 더 잘 풀었을 문제 ㅠㅠ package com.example.demo; import java.io.*; import java...

www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net Gold 5 dfs를 이용해서 풀었다. 주의 사항은 현재 상황을 기준으로 톱니바퀴가 움직인다는 것. 즉 만약 1번째를 움직이면 2번째도 움직이는데, 움직인 2번째가 3번째랑 만나서 움직이는 상황이 아니라는 것! 글로 설명이 어려운데, 현재 상황만 생각하지 움직임으로써 발생하는 연쇄 상황은 고려하지 않는다. 따라서, 움직일 상황을 다른 변수에 기록하고 그 변수를 사용하는 방식으로 사용되어야한다. 설명은 복잡한..

www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net Gold 3이지만 요청 사항 대로 구현만 하면 되는 문제. 1. 가로 세로 별로 새로운 배열을 만든다. 2. 현재 것과 그 다음 것의 높이를 비교한다. 1) 높이가 같다 -> 계속 진행 2) 높이가 2 이상 차이가 난다 -> 경사로를 놓을 수 없음 false 리턴. 3) 높이가 1 차이난다. 오르막인지 내리막인지 구분하여 경사로 길이만큼 놓을 수 있는지 확인한다. => 길이에 맞는지, 높이가 맞는지, 이미 놓여있지는 않는지. (배열 ..

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net gold 3 bfs 두번 사용해서 풀었다. 1. 여러 섬들을 구분한다. (dfs나 bfs이용해서 구분, 나의 경우엔 어차피 다 연결되어있는 거라 판단해서 bfs를 사용하였다.) 2. 바다이며(0인 경우), 주변에 섬인 경우(1인 경우) 다른 섬과의 거리를 파악한다.(최단 거리를 파악해야하기에 bfs를 이용한다.) 거리 배열을 따로 두어 거리를 파악하였다.(예전엔 무턱대고 cnt로 하였는데 이렇게하면 값이 어마어마하게..

www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net silver 4. 백트래킹으로 모든 경우의 수를 구해서 풀이하였다. 내가 헷갈려했던 것은 날짜 계산이었는데, 스케줄을 짜는 시점에서 마지막 날은 현재 날짜 + 기간이었는데 이 부분이 헷갈렸다. import java.io.*; import java.util.*; class Main { static int N, max; static int[][] works; static boolean[] visited; public static void main(String[] args) throws Exception { BufferedReader br = new B..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net Gold 5 문제 상황대로 풀이하면 되는 문제. 뱀이 성장한 만큼 이동인지 머리만 한칸씩 이동인지가 헷갈려서 시간이 오래걸렸다. 방향 전환과 문제의 종료 조건만 잘 구분해주면 됨. 방향 전환은 시간을 기록하고 그 시간에 방향을 바꿔주면 된다. 벽을 만나는 경우는 일반적인 bfs처럼 풀이하면 되고(해당 문제가 bfs 풀이는 아님) 뱀이 자신의 몸을 만나는지에 대한 풀이는, 나의 경우엔 뱀의 경로를 전부다 기록하고 뱀의 ..

www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 1. BFS로 풀이 2. 주어진 사항에 맞게 풀이하면 금방 풀 수 있음. import java.io.*; import java.util.*; class Main { static boolean[] visit = new boolean[10000]; public static void main(String[] args) throws Exception { BufferedReader br = new Buffe..

다익스트라 알고리즘을 공부하며 풀었던 문제! 왜 힘들어했는지 모르지만 공부 후 스스로 구현해 보며 상당히 어려워했었다. 1. PriorityQueue에 형식의 자료형을 넣어야 하는지를 제대로 이해하지 못했다. -> 속도를 위해 PriorityQueue를 써야하고 가중치를 기준으로 정렬되어야 한다. 2. 최단 경로를 저장하는 부분에서 프로세스에 대한 이해가 미흡.(뭔가에 씌였던 것인지 이해 불가임) while(!pQueue.isEmpty()) { Node cur = pQueue.poll(); visit[cur.v] = true; for (int i = 0; i < arrList[cur.v].size(); i++) { Node next = arrList[cur.v].get(i); //nextWeight : ..