boj, 백준) 16954. 움직이는 미로 탈출 ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 2. 문제 개요 8x8인 체스판에서 탈출하는 게임을 만들었다. 벽이 있는데 벽은 욱제가 움직일 때마다 밑으로 한 칸씩 움직인다. 욱제가 벽에 깔리면 게임은 끝난다. 욱제는 가만히 있거나 상하좌우 대각선으로 모두 9가지로 움직일 수 있다. 욱제의 캐릭터가 가장 왼쪽 아래에서 가장 오른쪽 위까지 이동할 수 있는지 없는지 구해보자. 3. 문제 힌트 시간개념을 더해보는 건 어떨까? 0초일 때..
boj, 백준) 10217. KCM travel ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 2. 문제 개요 M원 이하로 사용하면서 도착지까지 갈 수 있는 최단 경로를 찾는 문제. 1원이든, M원이든 M원 이내에만 들면 되고 그중에서 최단 시간으로 갈 수 있는 경로를 찾자. 3. 문제 힌트 DP를 사용해야 한다. 경로를 찾을 때는 다익스트라 알고리즘(logn)으로 구현해서 사용해야 한다. 어떻게 DP를 적용할까? 점화식을 찾기에 앞서 왜 DP를 써야..
boj, 백준) 2931. 가스관 (C / C++)
1. 문제 링크 www.acmicpc.net/problem/2931 2931번: 가스관 러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다. www.acmicpc.net 2. 문제 개요 가스를 M에서 Z로 옮기려고 파이프라인을 디자인하고 있다. 파이프의 종류는 다음과 같다. 파이프 라인의 설계를 마친 두 사람은 저녁을 먹으러 갔는데 그 사이 해커가 침입해 블록 하나를 지웠다. 지운 블록은 빈칸이 되어있다. 해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오. 3. 문제 힌트 맵의 총 크기는 25*25로 그렇게 크지는 않다. 어떤 파이프를..
boj,백준) 1039. 교환(C / C++)
1. 문제 링크 www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 개요 0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다. 1≤ i < j ≤ M 인 i와 j를 고른다. 그다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오. 3. 문제 힌트 그리디로 접근하려고 했으나..... 안 될 것 같다. 문제 유형을 보니 BFS..
boj, 백준) 20055. 컨베이어 벨트 위의 로봇 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 2. 문제 개요 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 1번 칸이 '올라가는 위치' N번칸이 있는 위치를 '내려가는 위치'라고 하자. 로봇은 '올라가는 위치'에서만 올라가고 '내려가는 위치'에서만 내려간다. 로봇이 올라가는 곳은(놓거나 걸어서) 내구도가 1 감소한다. 컨베이어 벨트를 이용해 로봇들을 건너편으로 옮..
boj, 백준) 20061. 모노미노도미노2 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 2. 문제 개요 및 풀이 kibbomi.tistory.com/172 boj, 백준) 19235. 모노미노도미노 ( C / C++ ) 1. 문제 링크 www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙 kibbomi.tistory..