사전학습 2일차 문제 풀이.
문제 상황
N 개의 숫자로 구성된 숫자열 Ai (i=1~N) 와 M 개의 숫자로 구성된 숫자열 Bj (j=1~M) 가 있다.
아래는 N =3 인 Ai 와 M = 5 인 Bj 의 예이다.
Ai 나 Bj 를 자유롭게 움직여서 숫자들이 서로 마주보는 위치를 변경할 수 있다.
단, 더 긴 쪽의 양끝을 벗어나서는 안 된다.
서로 마주보는 숫자들을 곱한 뒤 모두 더할 때 최댓값을 구하라.
위 예제의 정답은 아래와 같이 30 이 된다.
[제약 사항]
N 과 M은 3 이상 20 이하이다.
[입력]
가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
두 번째 줄에는 Ai,
세 번째 줄에는 Bj 가 주어진다.
[출력]
출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)
전체 구문
#1959. 두 개의 숫자열
def find_maxvalue(big_list, small_list, answer):
temp_value = 0
for i in range(len(small_list)):
temp_value += big_list[i] * small_list[i]
answer = temp_value if temp_value >= answer else answer
if len(small_list) < len(big_list): #재귀함수 실행
small_list = [0] + small_list
answer = find_maxvalue(big_list, small_list, answer)
return answer # 최종 최대값을 계산 후 리턴
tc = int(input())
for i in range(tc): #테스트케이스만큼 반복
answer = 0 #최종값
n, m = input().split()
input_a = list(map(int, input().split()))
input_b = list(map(int, input().split()))
if (len(input_a) >= len(input_b)): # 큰 리스트 찾기
big_list = input_a
small_list = input_b
else:
big_list = input_b
small_list = input_a
answer = find_maxvalue(big_list, small_list, answer)
print("#"+str(i+1), answer)
입출력단
#입출력단
tc = int(input())
for i in range(tc): #테스트케이스만큼 반복
answer = 0 #최종값
n, m = input().split()
input_a = list(map(int, input().split()))
input_b = list(map(int, input().split()))
if (len(input_a) >= len(input_b)): # 큰 리스트 찾기
big_list = input_a
small_list = input_b
else:
big_list = input_b
small_list = input_a
answer = find_maxvalue(big_list, small_list, answer)
print("#"+str(i+1), answer)
- 먼저 tc의 반복 입력 케이스를 받는다.
- 입력값을 토대로 for문을 수행. 한번의 시행 당 for문 한번이 수행된다.
- 입력받는 값은 다음과 같다. 숫자열의 크기 n,m / 두 개의 숫자열 값.
- 입력값을 토대로 리스트화 시키고, big_list와 small_list를 찾은 뒤 find_maxvalue 메소드를 실행한다. n,m 값은 추후 서술할 문제로 쓰지 않았다.
메인 메소드
def find_maxvalue(big_list, small_list, answer):
temp_value = 0
for i in range(len(small_list)):
temp_value += big_list[i] * small_list[i]
answer = temp_value if temp_value >= answer else answer
if len(small_list) < len(big_list): #재귀함수 실행
small_list = [0] + small_list
answer = find_maxvalue(big_list, small_list, answer)
return answer # 최종 최대값을 계산 후 리턴
- 입력받은 값을 토대로 지역변수 temp_value에 계산된 값을 저장한다.
- answer의 값과 비교하여 최댓값을 갱신시킨다.
- 숫자열 이동을 해야 하기에 if 조건문을 실행, 오른쪽으로 한 칸 shift하기 위해 계산 시 신경쓰지 않아도 되는 값인 0을 리스트 가장 첫 인덱스에 삽입한다. 이는 리스트 크기를 늘려 계산을 shift하게 된다.
- 동일 메소드를 다시 실행한다.
- 최종 값을 리턴한다.
문제 상황 - n, m 입력값 trouble (해결)
#입출력단
tc = int(input())
for i in range(tc): #테스트케이스만큼 반복
answer = 0 #최종값
n, m = input().split()
input_a = list(map(int, input().split()))
input_b = list(map(int, input().split()))
if (len(input_a) >= len(input_b)): # 큰 리스트 찾기
big_list = input_a
small_list = input_b
else:
big_list = input_b
small_list = input_a
answer = find_maxvalue(big_list, small_list, answer)
print("#"+str(i+1), answer)
입출력 단을 다시 확인해보겠다. 분명 n과 m의 숫자열 길이 int 변수를 받는 데까진 성공했다.
초기에는 '큰 리스트 찾기' if문에 해당 숫자를 이용했었다.
if (n >= m): # 큰 리스트 찾기
big_list = input_a
small_list = input_b
else:
big_list = input_b
small_list = input_a
다만 해당 경우 왜인지 모르겠지만 (n >= m)이 제대로 계산되지 않는 모습을 보인다.
실제로 input 값에
5 15
-8 4 6 -9 -1
-1 1 0 -2 10 10 0 2 5 2 10 7 -9 7 -8
을 대입한 경우이다.
해결) 단순한 문제였다. n,m 입력값을 받을 때 변수형을 지정하지 않아 str 타입으로 받아졌고, 이로 인해 조건문이 제대로 실행되지 않았던 이슈였다.
