Nanarin🙃

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 여러 방법을 써봤는데 다 시간초과... 입력 방법때문인가 싶어서 sys 모듈 readline 함수로도 바꿔봤는데 계속 시간초과가 난다 뭐때문일까?.. 그냥 너무 오래 걸려서 시간초과였음 ㅎ.. 머리가 다 굳어버린거같다 계속 시간초과나서 찾아봤는데도 이해가 안되서 한참 버벅댐 짧고 간단하게 풀리는 문제였는데 딕셔너리 너무 오랜만이라 더 그랬던 듯....

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 나는 아직 DP 문제에 적응을 못한거같다... 계속 혼자는 못풀겠다 ㅜ 아니 풀긴 푸는데 계속 시간초과나고 난리난리 입력받은 숫자를 앞에서부터 하나씩 셀것 입력받은 숫자들을 리스트 num에 저장하였다고 할 때 num[n] 과 num[n] + num[n-1] 을 비교하여 num[n] 에 저장한다 num[n]이 더 크다면 앞의 수들의 합 중 가장 큰 num[n] + num[n-1]이 더 크다면 예제 1번을 예로 들면 num ..

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 어우 너무 어려웠다 문제을 백번 읽어도 대체 이걸 어떻게 풀어야하나 모르겠는.. 그런... 그래서 찾아봤는데 DP의 유명한 문제라더라 LCS.. 아니나다를까 풀이 방법을 봤는데도 이해하는데 한참 걸렸다 다들 아... 이렇게 푸는구나만 설명하고 왜 이렇게 푸는지는 설명을 안해주셔가지고 너무 괴로웠다 뭐 설마 다들 풀이 방법을 보면 번쩍 하고 이유가 이해되는건가 나만 안..

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 허허 리스트에 교차점 다 넣고 지우고 넣고 빼고 난리난리를 쳤는데 반례를 없앨 수가 없어서 대체 어떻게 푸는건가 봤더니 참.. 세상에 이런 방법이..... 똑똑한 사람 개많다 증말 ㅜ 어쩐지 앞에 문제가 뜬금없다 했는데 써먹으라고 알려준거구나.... 없애야 하는 전깃줄의 최소 개수를 구한다는건 없애지 않고 그대로 놔둘 전깃줄의 최대 개수를 구하는 것과 같다 A 전봇대 기준 오름차순으로 정렬했을 때 B 전봇대에 연결된 ..

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분 수열은 앞 문제 11053번과 비슷하지만 조금 다르다 그냥 양쪽으로 계산해주면 된다 k개 원소를 가진 수열 = n번째 숫자 기준으로 0~n까지 가장 긴 증가하는 부분 수열 + n~k-1까지 가장 긴 감소하는 부분 수열 - 1 감소하는 부분 수열을 구하기 힘들기 때문에 수열을 뒤집어서 증가하는 부분 수열을 구한 후 다시 뒤집으면 감소하는 부분 수열이 된다 1. 입력받은 수들을 리스트 seq_1에 저장, seq_1을 복..

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 입력받은 수들을 리스트 seq에 저장 2. seq와 같은 길이의 t_seq를 생성하고 첫번째 요소는 1, 나머지는 0으로 채운다 => seq[n]까지의 가장 긴 증가하는 부분 수열의 개수를 리스트 t_seq[n]에 저장할 것 3. for문으로 t_seq[1] ~ t_seq[n-1] 까지 계산 => 가장 긴 수열에는 seq[n]가..

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2579 : 계단 오르기 문제랑 똑같이 풀면 된다 대신 계단은 마지막 계단을 꼭 밟아야 하지만 마지막 포도주를 마실 필요는 없기 때문에 맨 마지막 포도주의 최종 양이 아닌 리스트 중 최댓값을 출력해주면 된다 라고 생각했는데 이게 웬걸 대뜸 틀려버려서 뭐가 틀린건지 찾아봤는데 아니 n번째 포도주를 마시는데 대체 왜 n번째 포도주를 마시지 않는 경우가 고려사항에 포함된단 말인가? 세상에나 1도 이해 안가네 ... 그..

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. step[n][m] 에는 m으로 끝나는 n+1자리 계단 수의 개수를 저장할 것이다 2. step[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] 이다. ( 한자리 계단수는 1~9 ) 3. for문을 통해 2자리부터 n자리까지의 계단수를 구한다 3-1. n자리 계단수가 0으로 끝나려면 n-1자리 계단수가 1로 끝나야한다 3-2. n자리 계단수가 t(2~8) 로 끝나려면 n-1자리 계단수는 t-1로 끝나거나 t+1로 끝나야 한다 3-3. n자리 계단수가 9로 끝나려면 n-1자리 계단수가 8로 끝나야한다 3-..

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 처음엔 입력값이 너무 커서 순서대로 하면 무조건 시간초과 날 줄 알고 겁먹었다 근데 다른 방법이 떠오르지 않아서 일단 이전 dp문제들처럼 풀어봄 리스트에 각 숫자가 입력되었을 때의 최소 연산 수를 저장할 것! 그 숫자는 1을 빼거나, 3으로 나누거나, 2로 나눠야 한다. 그런데 연산 횟수의 최솟값을 구해야 하니까 1을 빼거나, 3으로 나누거나, 2로 나눴을 때 중 가장 작은 연산 횟수를 가진 연산을 행하면 된다. f(n) = min(f(n-1), f(n//3), f(n//2)) + 1 1. 리스트 num에 미리 n개의 0을 ..

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 앞에 문제들이랑 비슷했는데 이건 조금 헤맸다.. 다른 사람들이랑 같은 로직의 코드인데 계속 인덱스 에러가 나서 대체 왜그러나 했는데 stair랑 cost를 n까지만 저장해서 그랬다 n이 1인 경우랑 2인 경우에 리스트 인덱스 너머로 접근하니까 계속 오류가 난 것 ㅜ 이번에도 멍청했다... 1. 각 계단의 점수를 stair 리스트에 저장하고 각 계단에 도달할 점수의 최댓값을 저장할 cost리스트를 생성, 0으로 초기화 2. ..