전체 글

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 딱봐도 DP문제이다. 실버DP문제는 꽤 많이 풀어서 그런지 풀이가 한눈에 보인다. 해당 스티커를 선택할 수 있는 경우를 모두 고려해서 최대값을 dp값으로 저장하면 된다. 위의 경우를 점화식으로 작성하기만하면 끝이다. 스티커가 2줄이라 2차원 배열 쓰면 끝. 코드는 다음과 같다. #include #include #include #include #include #include #includ..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복을 이용한 거듭제곱이다. 예제를 봐보자. 10의 11승을 구해야하는데 원래 같았으면 10을 11번 곱해서 구했을 것이다. 하지만 분할정복을 사용하면 4번의 계산으로 구할 수 있다. ans = 10 * 10^2 * 10^83번처럼 보이지만 10^2에서 10^8까지 가는데 반복문이 2번돌기 때문에 4번이라고 하였다.10^11 = 10 * (10^5)^2 = 10 * (10 * (10^2)^2)^2 = 10 * (10 * (10 * 10)^2)^2위와 같이 제..

https://www.acmicpc.net/problem/12970 12970번: AB 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net A를 세팅해놓고 B가 하나 들어갈때마다 얼마나 변화가 일어나는지 구하면 된다. 구하는 과정이 수학적이라서 수학 태그가 붙은거 같다. 특별한 코멘트가 필요 없는 평범한 그리디 문제이다. 코드는 다음과 같다. import sys input = sys.stdin.readline N, K = map(int,input().split()) if (N // 2) * (N - N//2) < K: print(-1) for i in range(..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 배우고 적용하려는 참에 좋은 문제가 있어서 포스팅한다. 아마 well known일거 같긴한데 처음 접하는 문제라 기록에 남겨 놓는다. 시간복잡도가 그리 중요하지 않은 문제라 두가지 방법으로 모두 통과되어서 두가지 모두 소개하려고 한다. 1. N회 다익스트라 특정 마을에서 목적지 X까지 가야하므로 N-1번의 다익스트라가 필요하다. X에서 다시 마을..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 아주 유명한 well known 문제이다. 예전에 플레티넘 문제인 불 끄기에서 한번 접해봤던 문제이다. 그때 1열의 경우의 수에 대해서 1024가지를 고려했었다면 여기서는 첫번째 전구를 켜냐 끄냐로 나누어서 경우를 따져주어야한다. 여기서는 첫번째 전구 on off에 대한 것만 고려하면 되므로(2가지) 어렵지 않다. 그리고 앞의 전구가 만들려고 하는 전구와 다르면 버튼을..

https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 분명 그냥 수학문제로 간단해 보였는데 왜 틀렸는지 모르겠다. 처음에 한번 구현하고 왠만한것들 잘 통과 되길래 제출했는데 계속 틀렸다고 나와서 조금씩 수정하다가 스트레스 받아서 지우고 다시 짰더니 바로 통과... 알고리즘은 똑같이 짰는데 뭐가 틀린건지.. 코드는 다음과 같다. import sys import math input = sys.stdin.readline n ..