전체 글

[Python] 1793 - 타일링 (실버2)

1. 문제 설명 https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net 2. 아이디어 dp를 많이 써보지 않은 때라서 꽤 오랫동안 고민했었던 문제였다. 웃긴 건 풀긴 풀었는데 수학 문제 처럼 풀어버렸다가 다시 dp로 풀이해서 통과했다. 내가 처음 풀이한 방식은 top down 방식이고, 이 포스팅을 쓰면서 bottom up 방식 코드도 추가했다. 처음에 패턴을 못 찾아서 직접 모든 경우를 구하다 보니 일정한 규칙이 있음을 찾아냈다. 어째 피보나치 수열을 풀 때 dp를 쓰던 것과 흡사하게 생겼다 했더니 비슷한 풀이 방법으로 풀린다...

[Python] 2527 - 직사각형 (실버1)

1. 문제 설명 https://www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사 www.acmicpc.net 2. 아이디어 초,중학생 레벨의 간단한 수학 문제이다. 헷갈린다면 격자로 가로, 세로 선을 두 개씩 그어놓고 범위를 잘 판단해보면 된다. 아이디어라고 할 것이 딱히 없는 문제. 3. 코드 def solution(): for _ in range(4): x1, y1, p1, q1, x2, y2, p2, q2 = map(int, input().split()) if y1 > q2 or q..

[Python] 1713 - 후보 추천하기 (실버2)

1. 문제 설명 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 2. 아이디어 이게 한창 파이썬 공부 겸 알고리즘 공부할 때였기 때문에 del 연산을 처음 써봤었다. 구현 자체는 어렵지 않다. 문제 조건에 주는 대로 그대로 구현하면 된다. 추천한 후보를 순서대로 훑으면서 액자에 걸려있지 않다면 액자(result)에 걸고(append), 추천수는 cnt리스트에 따로 저장한다. 생각해보면 딕셔너리 같은 걸로 같이 묶어서 저장해도 나쁘지 않..

[Python] 1074 - Z (실버1)

1. 문제 설명 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 아이디어 일전에 다루었던 색종이 자르기 문제(BOJ - 2630)와 유사하다. 분할 탐색을 하되, 시간 제한이 0.5초밖에 안 되기 때문에 여유롭게 처음부터 읽고 있다가는 곧바로 시간 초과로 탈락할 수 있다. 사실 너무 뻔한 방법이다. 4분할을 했을 때 그곳에 내가 탐색하고자 하는 좌표가 포함되지 않는 사분면이라면 탐색하지 않고 건너뛰고, 해당 타일의 전체 개수만 계..