Nanarin🙃

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. ..

www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1149번이랑 같은 방식으로 접근하면 된다 1. 입력받은 수를 피라미드 형식의 이중 리스트 tri에 저장 2. 두번째 줄부터 한줄한줄 이전 줄에 자신을 선택 가능한 두가지 수 중 더 큰 수를 자신에 더한다 2-1. 첫번째 숫자는 이전 줄의 첫번째 숫자만이 자신을 선택할 수 있으므로 무조건 첫번째 숫자만 더해준다 2-2. 마지막 숫자는 이전 줄의 마지막 숫자만이 자신을 선택할 수 있으므로 무조건 마지막 숫자만 더해준다 3. tri의 마지막 줄에서 가장 큰 숫자를 출력한다 # 1932...

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 처음에는 RGB 각각 시작해서 3가지 루트를 계산해서 최솟값을 출력하도록 했음 각각 출발해서 RGB중 이전 위치 제외하고 남은 둘 중 작은값이랑 작은값 인덱스를 같이 리턴하는 함수를 만들어서 최종 값 최솟값을 출력하게 풀었음 하 예제도 뭐도 다 잘 나오는데 틀렸다고 해서 대체 뭐가 틀린건지 반례 다 찾아서 입력해봤는데 다 맞는거야 젠장 그래서 뒤지고 뒤져서 반례 찾았는데 같은 값이 들어오면..

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 그림을 보면 점화식을 구할 수 있다 보면 순서대로 1 1 1 2 2 3 4 5 7 9 12 … 인데 3부터 3 = 1 + 2 = w(1) + w(5) = w(6) 4 = 1 + 3 = w(2) + w(6) = w(7) 5 = 1 + 4 = w(3) + w(7) = w(8) 7 = 2 + 7 = w(4) + w(8) = w(9) 9 = 2 + 7 = w(5) + w(9) = w(10) 12 = 3 + 9 = w(6) ..