[python] 백준 1783 : 병든 나이트(자세한 풀이)

[python] 백준 1783 : 병든 나이트(자세한 풀이) 1783번: 병든 나이트 (acmicpc.net) 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 실버 4 그리디 접근 가로가 M, 세로가 N이다. N의 크기에 따라 나이트가 이동할 수 있는 경우의 수가 제한이 되는 부분이 있기 때문에 bfs대신 그리드를 경우의 수에 따라 나눠서 적용하는 방법을 사용해야 한다. 문제 조건에 따라 나이트가 이동할 수 있는 경우의 수는 다음과 같이 4가지이다. 문제 조건을 읽어보면, 나이트의 초기 위치는 반드시 맨 왼쪽 아래 구석에 있기 때문에 세로 N의 길이에 따라 나이트의 이동 패..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 13.
• textsms

[python] 백준 1543 : 문서 검색

[python] 백준 1543 : 문서 검색 1543번: 문서 검색 (acmicpc.net) 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 실버 4 브루트포스, 그리디, 문자열 접근 예제 입력1을 예시로 접근해보자. ababababa aba 첫줄에 입력한 글자를 인덱스 0부터 끝까지 탐색할 필요가 없다. aba라는 3글자가 첫줄에 입력한 문자열에 존재하는지 확인하는 것이기 때문에 맨 처음 인덱스부터 맨 끝에서 세번째 인덱스까지 탐색하면 된다. 따라서 for i in range(len(문자열변수) - len(찾을 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 12.
• textsms

[python] 백준 1049: 기타줄

[python] 백준 1049: 기타줄 1049번: 기타줄 (acmicpc.net) 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 실버 4 그리디 접근 먼저 기타줄의 브랜드가 여러개가 입력되었다면, 낱개 값의 가장 싼 값과 한팩 값의 가장 싼 값을 입력한 리스트로부터 골라낼 수 있어야 한다. 골라낸 두 값을 가지고 다음의 분기를 결정한다. 기타줄 낱개 가격 * 6 < 기타줄 팩이라면 무조건 낱개로만 기타줄을 사는게 싸게 친다. 그런데 기타줄 팩 하나를 사는게 더 이득이라면 최대한 기타줄 팩으로 많이 구입..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 9.
• textsms

[python] 백준 10610 : 30

[python] 백준 10610 : 30 10610번: 30 (acmicpc.net) 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 실버 5 그리디 접근 N의 입력값 크기나 너무나 크기 때문에 안의 숫자들을 어떻게 바꿔야할지 고민이 많았는데 그냥 다음의 조건들을 참고하면 쉽게 풀 수 있었다. N이 3의 배수임을 확인하는 법 : 각 자릿수의 총합이 3의 배수면 N은 3의 배수이다. 30의 배수를 찾아야 하기 때문에 N의 숫자 중에 0이 없으면 -1을 출력하도록 한다. 두 조건을 만족하는 숫자는 순서를 바꾸어도 3..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 7.
• textsms