[백준/Python] 2725. 보이는 점의 개수 & 15988. 1, 2, 3 더하기 3

밀린 데일리 레벨업 풀기 >_____ㅎ.....

 

 

 

1. 백준 2725. 보이는 점의 개수 

https://www.acmicpc.net/problem/2725

2725번: 보이는 점의 개수

 

문제

(0,0)에서 보이는 (x,y)의 개수를 구하려고 한다.(x,y >= 0, 정수)

(0,0)에서 (x,y)가 보이려면 (0,0)과 (x,y)를 연결하는 직선이 다른 점을 통과하지 않아야 한다. 예를 들어 (4,2)는 (0,0)에서 보이지 않는다. 그 이유는 (0,0)과 (4,2)를 연결하는 직선이 (2,1)을 통과하기 때문이다. 아래 그림은 0 <= x,y<=5인 경우에 (0,0)에서 보이는 점의 개수이다. 단, (0,0)은 계산하지 않는다.

N이 주어졌을 때, 원점에서 보이는 (x,y) 좌표의 개수를 출력하시오. (0 <= x,y <= N)

입력

첫째 줄에 테스트 케이스의 개수 C(1<=C<=1,000)가 주어진다. 각 테스트 케이스는 자연수 N(1<=N<=1,000) 하나로 이루어져 있고, 한 줄에 하나씩 주어진다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 (0,0)에서 보이는 점(x,y)의 개수를 출력한다.

CODE

import sys, math

input = sys.stdin.readline

dp = [0] * 1001
dp[1] = 3

for x in range(2, 1001):
    count = 0
    for y in range(1, x):
        if math.gcd(x, y) == 1:
            count += 1

    dp[x] = dp[x-1] + count * 2 # x, y 반대의 경우도 가능해서 그런 것으로 추정

for _ in range(int(input())):
    print(dp[int(input())])

• 어떻게 접근해야할지 몰라서 너무 해맸던 문제.
• 블로그 참고해서 답안 작성함.
• 핵심은 원점과 각 점이 가지는 기울기가 달라야 한다는 것 ➡️ 두 점 (x, y)의 최대공약수가 1이어야 하는 것
• 여러 경우가 입력되기 때문에 dp로 구현

 

---

 

2. 백준 15988. 1, 2, 3 더하기 3 

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

 

CODE

import sys

input = sys.stdin.readline

dp = [0] * 1_000_001
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 1_000_001):
    dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % 1_000_000_009

for _ in range(int(input())):
    print(dp[int(input())])

• 비슷한 문제를 풀어본 경험이 있어서 비교적 쉽게 구현함
• %1,000,000, 009를 하지 않음으로써 숫자가 길어지는 게 생각보다 시간을 엄청 늘리는 일인 것 같다.
  빼먹었다가 당황했음

 

- 끝! -