평범한 필기장

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 내가 생각한 풀이 나는 리스트의 각 지점까지의 증가하는 수열을 직접 만들어서 풀려고 했다. 아래 내 코드를 보면 i번째 이전의 수들을 리스트에 넣으려했다. 그 수가 수열의 마지막 수보다 크면 수열 리스트에 넣어 각 지점까지의 수열의 길이를 다 구하려 했다. 하지만 input 리스트가 1 3 5 100 101 77 78 ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 내 풀이방식 Dynamic Programming 방식을 이용했다. n이 5일때까지 직접 써보면 규칙을 발견할 수 있는데, n의 방법의 수는 n-1, n-2, n-3의 방법의 수를 다 더한 것이 된다. (이렇게 하나하나 해보면서 규칙을 찾아나가는게 맞는지는 모르겠다ㅜㅜ) 이 규칙을 그대로 구현만 하면 되는데, 엄청 간단하다! 내 코드 t = int(input()) for _ in range(t): n = int(input()) dp = [0, 1, 2, 4] for i in range(4, n+1..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 이 문제는 내가 아예 이해를 잘못해서 접근을 아예 잘못해서 틀렸다. import math n = int(input()) cnt = [] while True: # print(int(math.sqrt(n))) if int(math.sqrt(n)) not in cnt: cnt.append(int(math.sqrt(n))) n -= int(math.sqrt(n)) **..

https://www.acmicpc.net/problem/16206 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 내가 생각한 방식 예제 입력 4를 직접 해보면 알겠지만, 작은 수부터 잘라야 최대의 개수가 나오기 때문에 케이크 길이를 저장한 리스트를 오름차순으로 정렬한다. 케이크 길이가 10이 넘으면 10으로 자르고 10인 케이크 개수를 1개 늘린다. -> 케이크 길이가 10보다 작거나 같아질 때까지 반복 남은 케이크의 길이가 10이면 개수를 1개 늘린다. 케이크 리스트에 있는 모든 케이크에대해 ..

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 내가 생각한 아이디어 나는 이 문제를 너무 복잡하게 생각해서 자꾸 3번째 테스트 케이스에서 -1이 출력되었다. 기본적으로 틀린 부분을 기준으로 3*3 행렬부분을 바꿔야겠다는 생각은 했지만 그것을 적용하는 부분에서 내가 잘못 생각한 것 같다. 나는 3*3행렬에서 중심이 될 수 있는 점들을 골라내고 그 중심들을 모두 탐색해서 중심을 중심으로 3*3행렬 부분에서 틀린 부분이 있으면 그 행렬을 전부 바꿔야겠다는 이상한..

https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 내가 생각한 풀이방식 최소값을 구하는 방법 : K가 나오기 전까지 M의 개수를 카운트하고 K가 나오면 정답에 10 ** (그때까지 나온 M의 개수 - 1)을 이어 붙이고 5를 뒤에 붙여준다. 그리고 민겸 수가 K로 끝나면 앞의 방식대로 수행하고 그대로 정답을 출력하면 되지만 M으로 끝날 경우, 앞에서와 같이 정답에 10 ** (그때까지의 M의 개수 -1)을 이어붙인다. 최대값을 구하는 방법 : K가 나오기 전까지 M의 개수를 카운트하고 K가 나오면 정답에 5 * (10 ** ..