전체 글
-
백준 16937번 두 스티커PS 2020. 3. 15. 23:45
https://www.acmicpc.net/problem/16937 16937번: 두 스티커 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. www.acmicpc.net 모눈종이의 범위안에서 좌표마다 고려해주는 완전탐색으로 하면 시간초과가 납니다. 스티커는 2개만 붙입니다. 그러므로 스티커를 붙이는 형태를 강제할 수 있습니다. 1, 2 가 각각의 스티커라고 가정했을 때, 1 2 혹은 1 2 이렇게 말이죠. 단, 스티커가 회전하는 것도 고려해야 합니다. #include #include #include using namespace std; struct point { int y, x; }; int n, m, k, res; ..
-
백준 16638번 괄호 추가하기2PS 2020. 3. 15. 23:37
https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다. www.acmicpc.net 괄호가 가장 우선순위입니다. 그 다음으로 곱셈이 나머지 연산보다 우선순위입니다. 단순히 생각한대로 구현하기만 하면 되는 문제이지만 구현 디테일이 조금 까다로웠던 문제입니다. 저는 괄호만 일괄적으로 계산, 곱셈만 일괄적..
-
백준 17088번 등차수열 변환PS 2020. 3. 15. 23:29
https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]은 등차수열이 아니다. 수열 B = [B1, B2, ..., BN]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가 www.acmicpc.net 모든 수에 대하여 -1, 0, +1 연산을 적용시켜서 경우의 수를 계산하면 N의 크기가 10^5이기 때문에 시간 초과가 납니다...
-
백준 13913번 숨바꼭질4PS 2020. 3. 10. 20:41
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 탐색 문제입니다. 경로를 어떻게 저장할 것이냐가 문제입니다. 경로를 저장하기 위해 dfs를 사용해버리면 시간 초과가 날 것 입니다..
-
백준 13549번 숨바꼭질 3PS 2020. 3. 10. 19:00
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 기존의 숨바꼭질과 다르게 순간이동의 가중치가 0입니다. 즉, 큐에 들어가있는 가중치가 정렬되어 있지 않습니다. 이것을 해결하기 위..
-
백준 12851번 숨바꼭질2PS 2020. 3. 10. 18:55
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에서 2까지 도달한다고 합시다. +1, *2 이렇게 두 가지 방법이 있습니다. 즉, 탐색을 해가며 그 지점에 ..
-
백준 1697번 숨바꼭질PS 2020. 3. 10. 01:24
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 탐색 문제입니다. bfs로 풀었습니다. 범위 체크와 방문 체크가 필요합니다. #include #include #include using n..
-
백준 17825번 주사위 윷놀이PS 2020. 3. 9. 00:32
https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다. 게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에 www.acmicpc.net 완전 탐색 문제입니다. 백트래킹으로 순열을 구현하여 시뮬레이션 하면 됩니다. 윷놀이판의 저장 방법이나 윷놀이판의 순회 방법을 결..