https://www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 임의의 수 x, y를 잡았을 때, x%y == 0 이거나 y % x == 0이 되도록 수열 내의 원소를 바꾸어야하는데, 바꾸는 횟수가 최소가 되어야한다. 처음 접근했던 방식은 N의 범위가 1 ~ 5000이므로 반복문을 돌려 약수의 개수가 가장 많은 원소를 찾고, 해당 원소와 나누어지지 않는 원소를 바꾸는 방식이다. 그런데 코드를 돌려보니, 5 5 7 7 35 와 같은 원소가 주어졌을 때 제대로 출력이 되지 않는다는 것을 확인했고, 그래서 똑같이 반복문을 돌리되, 이번엔 약수의 개수가 아니라 나누어떨어지는 수의 개수를 구..
PS
https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 처음 문제를 읽었을 때 들었던 생각은 단순히 가장 긴 증가하는 부분 수열이었다. 그래서 열심히 LIS 코드를 짰는데, 이상하게 원하는 결과값이 출력이 되지 않았다. 그래서 임의로 사용한 예제 9 1 7 9 8 3 2 4 5 6 9 9 4 7 1 3 2 6 8 5 9 9 8 7 6 5 4 3 2 1 9 1 2 3 4 9 8 7 6 5 9 9 8 7 6 5 4 3 1 2 9 9 8 7 5 6 4 3 2 1 ..
https://www.acmicpc.net/problem/23084 23084번: IUPC와 비밀번호 치훈이는 인하대학교 빡코딩 대회, IUPC (Inha University Ppakcoding Contest)에 문제를 출제하고 있다. 대회에 낼 문제들은 극비사항이기 때문에, 치훈이는 문제가 저장된 컴퓨터에 비밀번호를 설정해 놓 www.acmicpc.net 종강 이후 거진 두 달만에 하는 PS 문제를 읽어보니 출력하는 문자는 모두 대문자이다. 처음 비밀번호보다 작은 길이의 문자열은 존재할 수 없다. 길이가 같은 문자열이라면 반드시 하나만 달라야 한다. 길이가 다르다면 해당 문자열이 존재하거나, 해당 문자열의 길이 - 1 이 일치하는 문자열이 존재해야 한다. 위 네 가지 조건만 만족하면 문자열을 쉽게 찾을..
https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net dp + dfs로 문제를 해결했다. 일단 처음에는 돌의 개수 100개, 문자 개수 20개, 천사와 악마 시작으로 2개가 존재하길래 재귀를 이용한 완전 탐색으로 접근했다. 그런데 코드를 짜면서 볼때는 몰랐는데, 시간초과가 난다고 해서 급히 노선을 바꾸었다. 시간초과가 나는 이유는 나중에 알았는데 (질문), 돌 100개, 문자열 20개가 모두 같은 언어로 이루어지면 결국 2 * 100 C 20이 되기 때문이었다..
https://www.acmicpc.net/problem/2737 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acmicpc.net 연속되는 자연수의 합으로 해당 정수를 표현할 수 있는지 묻는 문제 당연히 임의의 자연수를 i라고 하면, 연속하는 자연수이므로 i + 1, i + 2, ... 와 같이 연속된 자연수의 합으로 정수 N을 표현해야 한다. 먼저 자연수 2 개로 N을 표현할 수 있는지 생각해보면, 연속이 시작되는 자연수 (가장 작은 자연수)를 i라고 가정하고, i + (i + 1) == N이 되어야 하므로 ( N - 1 ) % 2i == 0 이 되어야 한다. 또한, ..
