https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 0-1 bfs 문제이다. 0-1 bfs란?? 그래프의 간선에서 가중치가 0과 1로만 이루어진 bfs 문제를 말한다! 이 문제가 해당 케이스이다. -1, +1, *2 위치를 체크하는 것은 bfs와 다를 바 없으나, 가중치가 0인 간선이, 가중치가 1인 간선보다 더 앞에 삽입되어야 한다! 가중치가 0이라는 것은, 아무 cost가 없다는 것을 의미하기 때..
https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 2x2x2 주사위와 3x3x3 주사위, 4x4x4 주사위를 그리면서 직접 세보면 패턴을 찾을 수 있다. 정육면체 주사위는 N==1 이 아닌 이상, 최소 1면 ~ 최대 3면까지만 볼 수 있다. import sys #sys.setrecursionlimit(10**6) input = sys.stdin.readline if __name__ == "__main__": N = int(..
https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net A와 B 1번 문제에 이어서 2번 문제이다. A와 B 1번 문제는 while문을 이용해 T에서부터 S를 만들어 나갈 수 있었지만, 2번 문제 같은 경우 while 문을 이용하기엔 다양한 경우의 수가 존재해서 재귀 + 브루트 포스를 이용해 풀었다. import sys #sys.setrecursionlimit(10**6) input = sys.stdin.rea..
https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 문제를 보면, 다음 수는 이전 수 * a + b이다. 이걸 잘 풀어보면 y = ax + b인 방정식으로 풀 수 있다. 여기서 x는 이전 수이고, y는 현재 수이다. 만약 아래와 같이 입력이 들어온다면, 2 = 1 * a + b인 것이다. 그렇다면 2를 f(1)로 표현할 수 있다! 5 1 2 3 4 5 여기서 a는 직선의 기울기를 의미하게 되는데, 기울기를 구하는 공식은 다음과 같다. 즉, f(2) - f(1) / 2 - 1 로 구할 수 있고, f(a)는 3이고 f..
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 진짜 순수 구현문제다.. 방향벡터를 이용해야하는 정도?만 제외하면.. 오랜만에 푸는 문제라 많이 어지러웠지만, 그래도 풀었다..! 문제의 해결방법은 다음과 같다 1. 미세먼지가 확산한다. 2. 공기청정기가 작동한다. 3. 위 과정을 T번 반복한다. 사실 2번은 정말 노가다..라고 할 수 있다. 그냥 값들을 앞으로 옮기기만 하면 되는데, for문이든 while문이든 취향껏 골라서 풀면 된다. 이제..
https://www.acmicpc.net/problem/2877 2877번: 4와 7 창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오. www.acmicpc.net 기사 공부하랴, 텝스 하랴 소홀히 했던 알고리즘을 정말 오랜만에 다시 풀어보았다. 4와 7로 이루어진 수 중, n번째로 작은 수를 출력하는 문제다. 단번에 아이디어가 떠오르지 않는데, 분명 패턴이 있을 것 같아서 찾을 때 까지 수를 계속 적어보았다. 문제에서 알 수 있듯, 이 문제는 이진수(0과 1로 이루어진 수)를 활용해 푸는 문제이다! 패턴을 살펴보자. 정수 1 = 이진수 1 = 4 정수 2 = 이진수 10 = 7 정수 3 = 이진수 11 = 44 ... 이런 ..
