Algorithm
-
[백준][14499번] 주사위 굴리기Algorithm/백준 2020. 4. 20. 23:27
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 결과 풀이과정 1. 주사위의 방향을 바꿔주는게 키포인트이다. 첫 주사위의 방향을 1, 2, 3, 4, 5, 6 순으로 정한다면 ..
-
[백준][3190번] 뱀Algorithm/백준 2020. 4. 19. 22:40
https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 풀이과정 1. 특별한 알고리즘없이 문제의 흐름대로 풀면 풀리는 문제였다. 2. 뱀의 길이가 계속 늘어 날 수 있어 vector를 이용하여 뱀의 ..
-
[백준][12100번] 2048 (Easy)Algorithm/백준 2020. 4. 16. 22:02
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 풀이과정 1. 완전탐색으로 풀었다. 2. 동,서,남,북 방향으로 맵을 이동시켰다. 결과 소스코드 더보기 #include #include enum DIRECTION { EAST, WEST, SOUTH, NORTH }; int map[20][20]; int N; int answer ..
-
[백준][13460번] 구슬 탈출 2Algorithm/백준 2020. 4. 13. 23:26
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 풀이과정 1. bfs로 풀었다. 2. R, B구슬은 동시에 움직이므로 동시에 같은방향으로 처리해줘야한다. 3. R, B를 이동시..
-
[백준][12851] 숨바꼭질2Algorithm/백준 2020. 4. 2. 22:25
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고 www.acmicpc.net 풀이과정 1. 이전 숨바꼭질1과 크게 다르지 않다. bfs를 통해 풀었다. 2. 한 step의 que가 비워지면 step이 증가한..
-
[백준][1697] 숨바꼭질Algorithm/백준 2020. 4. 2. 22:21
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 풀이과정 1. x + 1, x -1, x *2의 이동방향을 가지는 주인공이 도착지에 도착하는 가장 빠른 길이를 구하는 문제이다. 2. bf..
-
[SWEA][8424번] 유일한 사이클Algorithm/SWExpertAcademy 2020. 4. 1. 21:57
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWyxsBd6lyADFAVP SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 소스코드 더보기 #include #include #include using namespace std; vector map; int dp[1001]; int N; int answer = 0; void solution(int prev, int cur, int depth) { dp[cur] = depth; for (int i = 0; i < map[cur].size(); i++) { int next = ..
-
[SWEA][9092번] 마라톤Algorithm/SWExpertAcademy 2020. 3. 30. 23:08
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Opy-KWPoDFAWY SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이과정 1. 완전탐색으로 풀었다가 시간초과가 나서 Dp로 변경 2. 최대 K만큼의 구간을 건너 뛸 수 있으므로 dp[N][K]로 dp 사이즈 결정 3. dp[cur][K] = dp[next][K] + dis(cur, next) 와 같은 식을 구할 수 있다. 소스코드 더보기 #include #include #include #include #define MAX_VAL 0x7fffffff using n..