본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 11660번 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 22/09/17 이전에 누적 합 문제를 풀어 본 적이 있었는데, 그때를 경험 삼아서 이 문제도 풀 수 있을 것 같아 풀게 된 문제다. 전형적인 누적 합, DP문제이다. 문제 접근 방식: 표의 크기가 주어지고(N = ~1024) 쿼리의 크기가 10만까지 주어지는데, 한 쿼리 마다 표의 연산을 전부 처리한다는 극단적인 케이스를 가정한다면, 1024*1024*..
[Python] 1417번 국회의원 선거 https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 22/09/17 실버 5를 순서대로 밀던 도중에 만난 문제로, 그다지 어렵지는 않았던 문제였다. 한번 틀리긴 했으나, 단순한 문제 읽고 구현하는 문제로, 쉽게 생각하면 되는 문제였다. 문제 접근 방식: 문제 주인공인 다솜이는 사람들을 매수해서 국회의원에 당선이 되게끔 하려 한다. 당선 조건은 다른 모든 후보들보다 많은 투표수를 가지는 것. 이때 매수하는 최소의 사람을 구하는 것이다. 나..
[Python] 1402번 아무래도이문제는A번난이도인것같다 https://www.acmicpc.net/problem/1402 1402번: 아무래도이문제는A번난이도인것같다 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)이 주어진다. 테스트 케이스마다 두 정수 A, B(-231 ≤ A, B ≤ 231-1)가 주어진다. www.acmicpc.net 22/09/16 이 문제는 풀고 나서 정말 감탄했던 문제이다. 아이디어가 기가 막히는 문제이다. 문제 접근 방식: 문제는 굉장히 짧고 간단하다. 어떤 정수 $A$가 있으면 그 숫자를 $A = a_1 * a_2 * a_3 * \cdots * a_n$으로 했을 때 $A' = a_1 + a_2 + a_3 + \cdots + a_n$이 성립하면 "$A$는 $A'$으로 변할 수 있다"라고 한다. ($a_i$는 정수) 만..
[Python] 1384번 메시지 https://www.acmicpc.net/problem/1384 1384번: 메시지 그룹 번호를 "Group 1"과 같이 출력함으로써 출력을 시작합니다. 그 다음 줄부터 누가(A) 누구(B)에게 나쁜 말을 했는지 "A was nasty about B"로 한 줄씩 출력합니다. 나쁜 말이 여러 개라면, 입력받은 순 www.acmicpc.net 22/09/16 맨 처음에 예제가 이해가 잘 가지 않았던 문제로, 게시판을 보고 이해할 수 있었다. 이 문제를 보고 앞으론 문제의 지문을 잘 읽어야겠다는 생각을 하게 되었다.... 문제 접근 방식: 누가 누구에게 나쁜말을 했는지 순서대로 출력하면 되는 문제이다. 예제를 보면 이해가 쉬운데, 예제 입력과 출력을 보자. Ann P N P P Bob P P P P Cliv..
[Python] 1380번 귀걸이 https://www.acmicpc.net/problem/1380 1380번: 귀걸이 입력은 번호를 가진 시나리오들로 구성됩니다. 시나리오 번호는 1부터 순서대로 증가하고, 각 시나리오는 아래의 내용을 포함합니다. 한 줄에 귀걸이를 압수당한 여학생의 수, n (1 ≤ n ≤ 100)이 www.acmicpc.net 22/09/16 마찬가지로 실버 5를 밀던 도중 만난 문제로, 개인적으로 문제의 입력이 이해가 되지 않았던 문제였다. 문제 접근 방식: 테스트 케이스 하나당 여학생 수가 주어지고, 여학생들이 주어진다.(여학생들의 리스트가 주어진 순서대로 여학생들을 번호로 간주한다.) 이후 여학생들이 목걸이를 빼앗겼다가 다시 되찾는 것을 숫자와 A 또는 B로 구분하여 준다. 숫자가 처음 나오는 것이면 빼앗기는 것..
[Python] 1340번 연도 진행바 https://www.acmicpc.net/problem/1340 1340번: 연도 진행바 평년일 때, 각 달은 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31일이 있다. 윤년에는 2월이 29일이다. 윤년은 그 해가 400으로 나누어 떨어지는 해 이거나, 4로 나누어 떨어지면서, 100으로 나누어 떨어지지 www.acmicpc.net 22/09/16 이 문제 또한 실버 5 밀기 중 만난 문제로, 실버 5치고는 재미있게 풀었던 문제였다.(난이도가 살짝 높지만, 실버 4 수준 정도는 아니라는 뜻) 문제 접근 방식: 날짜를 입력 받으면, 그 년도를 기준으로 하여 현재 날짜가 몇 퍼센트 지나갔는지를 출력하는 간단한 문제이다. 이 문제에선 윤년을 판단해야만 했기 때문에 cale..
[Python] 18155번 Issuing Plates https://www.acmicpc.net/problem/18155 18155번: Issuing Plates Your output will be M lines, one per plate, in the same order as the plates are given on the input. If the plate is valid, write out the string ‘VALID’; otherwise write out the string ‘INVALID’. www.acmicpc.net 22/09/16 실버 5 밀기에 도전해보고자 하여 순서대로 밀던 중 만난 문제이다. 간단한 문자열 문제로, 쉽게 풀 수 있었다. 문제 접근 방식: 문제는 굉장히 간단한데, N개의 문자열 세트와 판별해야 할 M개의 문자열 쿼리가..
[Python] 1308번 D-Day https://www.acmicpc.net/problem/1308 1308번: D-Day 첫째 줄에 오늘의 날짜가 주어지고, 두 번째 줄에 D-Day인 날의 날짜가 주어진다. 날짜는 연도, 월, 일순으로 주어지며, 공백으로 구분한다. 입력 범위는 1년 1월 1일부터 9999년 12월 31일 까지 이다. www.acmicpc.net 22/09/16 간단한 구현 문제로, 프로그래밍 기초를 배우면 자주 접하는 윤년 판단 문제가 응용된 문제이다. 문제 접근 방식: 파이썬의 datetime모듈을 사용하여 구현하였다. 1000년을 넘어가면 'gg'를 출력해야 하므로 그 부분은 따로 처리를 먼저 해주었고, 나는 윤년 처리가 귀찮았기 때문에 datetime의 toordinal 메서드를 활용하였다. 이 메서드는 1년 1..

티스토리툴바