...
백준 2287 - 모노디지털 표현 - swift
https://www.acmicpc.net/problem/2287 2287번: 모노디지털 표현 몇 개의 숫자 K(K는 1, 2, …, 9중 하나)와 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈)만을 사용하여 어떤 자연수 X를 수식으로 표현한 것을 X의 K-표현이라 부른다. 수식에는 괄호가 포함될 수 있으며, 나 www.acmicpc.net 조합과 dp를 이용한다. 사칙연산으로 경우의수를 고려하다보면 골치아파진다. 물론 사칙연산으로 경우의수를 고려하긴해야하는데, 이는 4가지경우의수로만 한정짓고, K가 몇개사용됐는지를 중점으로 경우의수로 고민하면 풀린다. K는 최대 8개까지사용할수있다고했다. 또한 문제에서 K가 연속으로 붙어있는경우도 존재한다. 그러므로, K가 1개, 2개, 3개...8개 사용했을때 모든경우의수를..
백준 1351 - 무한수열 - swift
https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 선뜻보면 감이안온다. 심지어 N이 1조이다. 1부터 증가시켜서 찾을수도없다. 이 수열은 분명 재사용되는 값이 존재할 것 같지만, N이 1조안에서 dp를 적용해도 효율적일까 싶다. 결론은 효율적인데, 그 이유는 P와 Q의 범위를 보고 알 수 있다. P,Q는 최소 2이상이다. 또한 수열특징이 P or Q로 나눈 값이다. 즉, 최소 P,Q가 2라고 가정했을때, 매번 2로 나누어진다는 점이고, 이는 log2 로 계산할수있다. 즉, log2 ( 1조 ) 는 약 39로, 39번의 횟수로 1조에서시작하여 0으로 도착하는걸 알 수 있다. 2로 했는데도 ..
백준 1508 - 레이스 - swift
https://www.acmicpc.net/problem/1508 1508번: 레이스 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주 www.acmicpc.net 주어진 조건을 보면 심판들은 정해진위치에만 서있을 수 있다. 정해진위치( K )의 개수는 최대 50개이다. 그렇지만 심판들( M )의 개수는 최대 만개이다. 여기서 알수있는 사실은, M이 K보다 크거나같다면, 무조건 특정위치에 여러명의 심판들이 존재할수밖에 없다는 사실이다. 이 경우에 답은 무조건 1로 채워진 문자열이여야할 것 이다. 여기서 어떻게 접근해야할까, 정..
