BOJ10523 직선 찾기

문제 링크 : https://www.acmicpc.net/problem/10523

문제 요약

N개의 점이 좌표 평면 상에 있을 때, 이 중 p 퍼센트 이상의 점들을 지나는 직선이 존재하는지 판별하는 문제다.

문제 풀이

만약 조건을 만족하는 직선이 존재한다면 랜덤하게 두 점을 집었을 때 그 두 점이 만족하는 진선 위에 있을 확률은 \( p^2 \) 일 것이다. 문제에서 \( p >= 0.2 \) 이므로 몬테카를로 알고리즘을 적용 시킬 수 있다.

N=1인 경우에 유의하자.

소스코드 (c++)

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REP2(i,s,e) for(int i=s; i<e; i++)


#define ll long long
#define pii pair<int, int>

#define x first
#define y second

int n, p;

int count(vector< pii > &pts, int p, int q)
{
    pii vec_pq = {pts[q].x-pts[p].x, pts[q].y-pts[p].y};

    vector< pii > others;
    int r = 0;
    for(pii &pt : pts)
    {
        pii vec_v = {pt.x-pts[p].x, pt.y-pts[p].y};
        if(1LL*vec_pq.x*vec_v.y - 1LL*vec_pq.y*vec_v.x == 0) r++;
    }

    return r;
}

int main()
{
    scanf("%d%d", &n, &p);
    vector< pii > pts(n);
    REP(i, n) scanf("%d%d", &pts[i].x, &pts[i].y);

    bool flag = false;
    knuth_b gen;
    int iter = 100;

    if(n == 1) flag = true;

    if(n < 100)
    {
        REP(i, n) REP2(j, i+1, n)
        {
            flag |= count(pts, i, j)*100 >= n*p;
            if(flag) break;
        }
    }

    while(iter--)
    {
        int x = gen() % n;
        int y = gen() % n;
        if(x == y) continue;

        flag |= count(pts, x, y)*100 >= n*p;
        if(flag) break;
    }

    printf("%s\n", flag ? "possible" : "impossible");


    return 0;
}

BOJ11057 오르막 수

1. 문제링크 : BOJ11057 : 오르막 수

2. 문제요약

 - 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. (인접한 수가 같아도 오름차순으로 친다)
 - 예를 들어, 2234, 3678은 오르막 수이지만, 2232, 91111은 오르막 수가 아니다.
 - 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 것이 목표이다.
 - 수는 0으로 시작할 수 있다.

3. 문제풀이

 - Dynamic Programming을 이용한다.
 - dp[i][j]를 <길이가 i이고 끝자리가 j인 오르막 수의 개수>로 정의한다.
 - 인접한 수가 같아도 오름차순이라고 생각하므로, dp[i][j]는 (길이가 1 작으면서 끝자리가 j인 오르막 수의 개수) + (길이는 같으면서 끝자리가 j - 1인 오르막 수의 개수)가 된다.
 - 즉, dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이다.
 - 이 점화식을 반복문으로 구현해 goal인 sum(dp[n][i], 0 < i < 10)을 구한다.

4. 소스코드 ( C++ - 헤더파일을 제외하고 C와 같음 )
 

BOJ9505 맥주 마시면서 걸어다니기

1. 문제링크 :  BOJ9505 : 맥주 마시면서 걸어다니기

2. 문제요약

 -  송도에 사는 상근이와 친구들은 맥주를 마시면서 걸어가기로함, 상근이네 집에서 출발      하여 맥주 한 박스를 들고 출발한다.
 - 맥주 한 박스에는 맥주가 20개 들어있는 상황, 이동중에 50미터에 한 병씩 맥주를 마심
 - 도착지 까지 맥주를 마시면서 가되, 중간에 맥주를 파는 편의점에서 맥주를 구매 가능하     지만 편의점에 들렸을 때 빈 병은 버리고 새 맥주병을 살 수 있음.
 - 박스에는 20병 넘게 맥주를 담을 수 없다.

 Goal : 상근이가 도착지까지 맥주를 마시면서 도착 할 수 있는가 판단하기

3. 문제풀이

 - 다양한 풀이법이 존재하겠지만 본 풀이에서는 DFS를 이용하였다.
 - 편의점이 N개 존재할때, 시작지점을 0번 노드, 편의점을 1~N 번노드, 도착지점을 N+1       번  노드라고 가정하였다.
 - 이때 DFS를 이용하여 0번 노드에서 시작하되, 20병의 맥주를 소모해서 갈 수 있는 거리      (2000) 이내에 존재하는 노드를 방문하여 최종 지점까지 방문해간다.
 - 만약 N+1 번 노드에 도달 할 수 있다면 맥주를 마시면서 도착이 가능하고 N+1번 노드       에  도달이 불가능 하다면 도착이 불가능하다.

4. 소스코드 ( C )

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node{
    int x;
    int y;
}node;

bool result=false;

node set[102];
bool check[102];

int n;

void dfs(int m){
    check[m]=true;
    if(m==n+1)
    {
        result = true;
        return ;
    }

    for(int i=1;i<=n+1;i++){
        int distance=abs(set[i].x-set[m].x)+abs(set[i].y-set[m].y);
        if(check[i]==false&&distance<=1000){
            dfs(i);
        }
    }
}

int main(void){
    set[0].x=0;
    set[0].y=0;

    int t;
    scanf("%d",&t);

    for(int z=0;z<t;z++){
        memset(check,false,sizeof(check));
        result=false;
        scanf("%d",&n);
        for(int i=0;i<=n+1;i++){
            scanf("%d %d",&set[i].x,&set[i].y);
        }
        dfs(0);
        if(result)
            printf("happy\n");
        else
            printf("sad\n");
    }
    return 0;
}

BOJ2989 개구리 왕눈이

문제 링크 : BOJ2989

문제 요약

2차원 좌표에 점들이 있고 각 점에는 파리가 있다. 개구리는 처음에 힘이 0이고 파리를 먹어서 먹은 만큼 힘을 증가 시킬 수 있다. 1번점부터 시작하여 점에서 점으로 이동하여 N번째 점에 도착했을 때 힘이 최대가 되어야 한다. 점에서 점으로 이동 하려면 X좌표 또는 Y좌표가 같아야 하며 좌표가 증가해야 한다. 이동 할 때 마다 힘이 K만큼 감소하고 이동하는 도중에 힘이 음수가 되면 안된다.

위 이미지는 예제를 시각적으로 표현한 이미지이다. 왼쪽 하단의 노란색점이 1번점이고 오른쪽 상단의 노란색점이 N번째 점이다. 화살표는 점에서 점으로 갈 수 있는 방향을 의미하며 점에 쓰여있는 숫자는 파리의 양을 의미한다.
파리가 30만큼있는 점을 지나는 경로로 이동하면 최대일 것 같지만 힘이 부족하여 30만큼있는 점으로 이동 할 수 없다. 따라서 파리가 5만큼있는 점들을 지나서 이동하는게 최적이자 유일한 방법이고 N번째 점에 도달 했을 시 힘이 5가 된다.

문제 풀이

우선 점들을 좌표 기준으로 정렬하면 이동할 수 있는 경로는 사이클이 없는 구조임을 알 수 있다. (항상 좌표가 증가하는 방향으로 이동해야 하기 때문이다.)

DP[i] = 1번점부터 i번째 점까지 왔을 때 최대 힘

이라고 정의하면 간단한 \( O(N^2) \) 풀이를 떠올릴 수 있다. 하지만 N이 너무 커서 좀 더 효율적으로 계산 할 방법을 찾아야 한다. DP[i]를 계산할 때 다른 점들을 전부 볼 필요가 없다. X좌표가 같은 점들 중 DP[j]가 최대인 것과 Y좌표가 같은 점들 중 DP[j]가 최대인 것만 보면 된다. 이를 빠르게 알 수 있도록 보조로 xMX라는 배열을 만들어 xMX[x]에는 좌표가 x인 것 중에서 DP[j]값이 제일 큰 것을 저장하도록 한다. y좌표도 마찬가지로 처리 할 수 있다.
좌표를 기준으로 정렬 했으므로 처음과 순서가 다름에 유의하자.

소스코드 (Python3)

intINF = 10 ** 18
coordMX = 10 ** 5 + 1

if __name__ == "__main__":
    n, k = map(int, input().split())
    lotuses = []

    for i in range(n):
        lotuses.append(list(map(int, input().split())) + [i])

    lotuses.sort()

    xMX = [-intINF] * coordMX
    yMX = [-intINF] * coordMX
    xMXidx = [-1] * coordMX
    yMXidx = [-1] * coordMX
    dp = [-intINF] * n
    prv = [-1] * n
    destIdx = -1

    for i in range(n):
        x, y, flies, id = lotuses[i]

        if id == n-1: destIdx = i

        if id == 0: dp[i] = flies
        else:
            if xMX[x] >= k and xMX[x] - k + flies > dp[i]:
                dp[i] = xMX[x] - k + flies
                prv[i] = xMXidx[x]

            if yMX[y] >= k and yMX[y] - k + flies > dp[i]:
                dp[i] = yMX[y] - k + flies
                prv[i] = yMXidx[y]

        if xMX[x] < dp[i]: xMX[x], xMXidx[x] = dp[i], i
        if yMX[y] < dp[i]: yMX[y], yMXidx[y] = dp[i], i

    print(dp[destIdx])

    cur = destIdx
    path = []

    while cur != -1:
        path.append(cur)
        cur = prv[cur]

    path = path[::-1]

    print(len(path))
    for idx in path:
        print(lotuses[idx][0], lotuses[idx][1])