내맘대로블로그

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 : ..

www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 문제 풀이 방식은 위상 정렬 풀이 방식과 흡사하다고 생각했다. 간단한 순서가 있어서 ArrayList를 이용하여 값을 넣어준 후, BFS를 이용하여 풀이를 해주었다. 이 문제에서 1. 적절하게 값 넣기 (이 생각이 제일 어려웠음) 2. 문제를 잘 부분을 나눠서 꼼꼼하게 코딩하기 이걸 잘 생각한다면 나름 평이한 문제라고 생각이 든다. import java.io..