링크 : https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 문제 소요시간: 30분(실패) 설계하기(접근방법) 1. 입력받기 list(map(int, str(input()))) 을 통해 int를 공백없이 리스트로 슬라이싱 가능하다 2. 구현하기 처음과 끝 리스트를 어떻게 나누어 구현하는가에 생각을 많이했다. 이 문제의 핵심은 가운데를 기준으로 이전의 인덱스가 목표 리스트의 인덱스와 같지 않다면 뒤집어주는 것이다 그리디로..
링크 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 문제 소요시간: 30분(15점), 35분(놓친 케이스 참고 : 100점) 설계하기(접근방법) 1. 입력받기 문자열을 입력받는다 2. 구현하기 이 문제의 핵심은 가장 끝쪽의 연속된 문자열은 문자 한개랑 같다는 것이다. 즉 BRBBBR나 BRBBBRRRR이나 옮겨야 하는 문자열의 수는 같다는 것이다 우측을 예시로 R이나 RRRR이든 RRRRRRRR이든 옮겨야 하는..
링크 : https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 문제 소요시간: 15분(아이디에이션 실패) 설계하기(접근방법) 1. 입력받기 행렬을 기존 행렬과 목표 행렬로 나누어 입력받는다 2. 구현하기 먼저 3*3의 배열을 뒤집을 수 있는 기능을 구현한다 range(3)의 이중 for문을 구현해서 x = 1 - x의 방식으로 뒤집는다 이 문제의 핵심은 한번 지나간 행렬은 다시는 뒤집지 못한다는 것이다 즉 그리디 알고리즘처럼 지금 당장 뒤집으면서 문제를 해결해나가..
링크 : https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 소요시간: 23분 12초 설계하기(접근방법) 1. 입력받기 문제의 조건대로 입력받는다 2. 구현하기 먼저 주가 리스트의 가장 1번째 원소가 최댓값인 경우 주식을 살 필요가 없으니 바로 0을 출력해준다 아니라면 리스트의 최대값을 기준으로 차액을 더해 나가고 최대값을 만나면, 그 다음 인덱스부터 끝까지의 최대값을 새로 구한다 이 새로운 최대값의 차액을 이익으로 더해나간다 +..
링크 : https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 문제 소요시간: 8분 40초 설계하기(접근방법) 1. 입력받기 입력 조건을 입력받는다 2. 구현하기 물건을 가장 싸게 사는 방법은 비싼 물건 순으로 정렬하여 묶는 것이다 한 묶음에서 가장 저렴한 상품의 가격이 제거되니 비싼 묶음에 싼 물건 하나가 존재하면 손해를 본다 sort()를 통해 정렬한 후 for문을 통해 3번 째 물건들의 가격은 더하지 않는다 3. 출력하기 가격을 출력..
링크 : https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M basket_location[-1]: while apple_location not in basket_location: for j in range(len(basket_location)): basket_location[j] += 1 distance += 1 continue print(distance) 얻어갈 부분 1. 입력하는 변수가 2줄이었는데 1줄로 읽고 이동거리가 정답과 맞지 않아서 크게 혼동했다. 입력조건을 차분하게 읽는 습관을 들이자
링크 : https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 소요시간: 7분 35초 설계하기(접근방법) 1. 입력받기 거스름돈을 입력받는다 2. 구현하기 수학적으로 접근했다. 둘의 최소공배수인 10을 넘어가는 경우, 거스름돈을 거슬러주지 못하는 경우는 없으므로 10 아래의 경우의 수만 고려해서 while문을 돌렸다. 1,3 인 경우 거슬러줄 수 없고 2,4,6,8인 경우 각각 1,2,3,4,를 몫으로 동전 개수에 더해준다 5, 7, 9 혹은 그 이상은 while문으로 반복하면서 개수를 구할 수 있다 3. 출력하기 동전의 개수를 출력한다 코드(출력) n = int..
링크 : https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 문제 소요시간: 21분 36초 설계하기(접근방법) 1. 입력받기 문자열을 입력받는다 2. 구현하기 구현 문제를 많이 풀다보니 그대로 구현해버렸다. 파이썬의 replace 함수를 사용하면 매우 쉽게 풀 수 있지만 구현한 내용은 다음과 같다 앞에서부터 X의 개수를 세서 리스트에 넣는다 '.'도 '.'으로 리스트에 넣어준다 리스트를 순회하며 int인 경우 4의 배수 이면 'AAAA'를 아니라면 'AAAA'를 4로 나눈 몫만큼 출력 후 'BB'를 출력한다 '.'인 경우 '.'을 출력한다 만약 홀수가..
