2018년 6월 9일 토요일

BOJ11986 스탬프렐리-2

문제 링크 : BOJ11986

문제 요약

J, O, I로 이루어진 이루어진 문자열이 주어진다. 이 때 문자 하나만 추가하여 부분문자열 (Subsequence)중에서 "JOI"의 개수가 최대가 되도록 해야한다.

예제 1
5
JOIOI
의 경우 앞에 J를 붙여 6개를 만들 수 있다.

문제 풀이

추가하는 문자가 J인 경우 제일 앞에 붙이는게 이득이고 추가하는 문자가 I인 경우 제일 뒤에 붙이는게 이득이다. 만약 O를 추가해야 하는경우라면 추가된 기준으로 (왼쪽에 있는 J의 개수) * (오른에 있는 I의 개수) 만큼 추가 된다.

우선 경우의 수를 계산하는 함수를 calc라 하고 기존의 문자열을 S라고 하자. 추가로 count(i, j, c)는 i번째 문자와 j번째 문자 사이에 있는 문자 c의 개수라고 하자.

calc은 간단한 \( O(n) \) DP, count(i, j, c)는 전처리 후 \( O(1) \) 만에 구할 수 있다.

답은
$$ max(calc('J'+S), calc(S) + count(1, i, 'J') * count(i, n, 'I'), calc(S + 'I')) $$

소스코드 (C++11)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll calc(string s)
{
    ll j=0, o=0, i=0;
    for(char c : s)
    {
        if(c == 'J') j++;
        else if(c == 'O') o += j;
        else if(c == 'I') i += o;
    }
    return i;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    string s; cin >> s;
    ll res = 0, base = calc(s);
    int j=0, i=count(s.begin(), s.end(), 'I');
    for(char c : s)
    {
        if(c == 'J') j++;
        else if(c == 'I') i--;
        res = max(res, base + 1LL*j*i);
    }
    cout << max({res, calc("J"+s), calc(s+"I")}) << endl;
    return 0;
}

2018년 6월 1일 금요일

BOJ 10250 ACM 호텔

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

2. 문제 요약
- H x W의 크기를 가진 호텔에서 다음 손님이 들어갈 방을 배정(높이 x 너
- 손님들은 101호, 201호, ... W01호, 102호 ... 순으로 선호함

3. 문제 풀이
- 3 x 4의 호텔에서 5번째 들어갈 손님은
   5%3 층
   5/3    호 (반올림) 이 된다

4. 소스코드(c)
#include <stdio.h>
#include <math.h>

int main(void)
{
int i;
int caseCount;
int hotel[100][100] = {0, };
int heightCount, widthCount;
int width;
double customerIndex;
double height;

scanf("%d", &caseCount);
for (i = 0; i < caseCount; i++) {
scanf("%d %d %lf", &heightCount, &widthCount, &customerIndex);
height = (int)customerIndex%heightCount;

if (height == 0)
printf("%d", heightCount);
else
printf("%d", (int)height);

width = ceil(customerIndex/heightCount);
if (width < 10)
printf("0%d\n", width);
else
printf("%d\n", width);
}


return 0;
}

2018년 5월 27일 일요일

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;
}

2018년 5월 15일 화요일

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와 같음 )
 

2018년 5월 13일 일요일

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;
}



2018년 5월 12일 토요일

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])

2018년 4월 29일 일요일

실수 연산 피하기

문제를 풀다보면 실수 연산을 해야 할 때가 있습니다. 하지만 실수 연산에는 실수 오차가 생겨 결과가 부정확 해질 수 있으며 정수 연산에 비하여 연산 횟수가 많음으로 가능하다면 피하는 것이 좋습니다.

1. double 대신 long long 쓰기
long long 는 -2^62 부터 2^62 - 1까지의 정수들을 저장 할 수 있는 타입입니다. 만약 계산과정이 모두 long long 범위 안에 있고 정수 연산만 필요한 경우 long long을 쓰는 것이 좋습니다.

2. 제곱근 비교
소수인지 판별하기 위하여 흔히 n을 2부터 sqrt(n)까지 나눠봅니다. 비교하는 양변이 모두 양수이므로 제곱하여 정수 연산만으로 i가 sqrt(n)보다 작거나 같은지 비교 할 수 있습니다.
for(int i=2; i<=sqrt(n); i++)

for(int i=2; i*i<=n; i++)

3. 분수 비교
A, B, C, D 모두 정수이고 A/B > C/D 인지를 판별하고자 한다면 다음과 같이 쓸 수 있습니다.
if(1.0*A/B > 1.0*C/D) 

if(A*D > C*B) 


4. 분수의 올림값 계산하기
A, B가 정수고 A/B의 올림값을 계산하고자 할 때 다음과 같이 쓸 수 있습니다.
int C = ceil(1.0*A/B)

int C = (A+B-1)/B

2018년 4월 26일 목요일

BOJ9012 괄호

문제 요약
입력된 괄호가 올바른 순서를 따르고 있는지를 알아보는 프로그램을 작성하세요.

문제 풀이
스택을 이용합니다.
우선 올바른 괄호라면, 스택이 다음과 같이 처리됩니다.
1. '('를 만나면 반드시 여기에 맞는 ')'가 나와야 하므로, 스택에 push한다.
2. ')'를 만나면 반드시 여기에 맞는 '('가 스택에 들어있어야 하므로, 스택을 pop한다.
3. 입력된 문자열을 모두 처리하고 나면, 스택은 비어 있어야 한다.

잘못된 괄호라면, 다음과 같은 상황이 일어납니다.
1. '('가 나오지 않았는데 ')'가 먼저 나온다. -> 비어 있는 스택에서 pop을 시도한다.
2. '('에 맞는 ')'가 부족하다. -> 입력된 문자열을 모두 처리했는데, 스택이 비어 있지 않다.

주의할 점
스택의 위치를 표시하는 top이 연산 과정에서 -1 -> -2 -> -1로 가는 경우가 발생할 수 있으므로, 잘못된 상황이 벌어지면 루프문에서 바로 빠져나와 잘못되었다는 판단을 한다.


C 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n = -1;
void push(int* stack)
{
 stack[++n] = 1;
}
int pop(int* stack)
{
 if (n >= 0)
  return stack[n--];

}

int empty(int* stack)
{
 return n == -1 ? 1 : 0;
}

int main(void)
{
 int num;
 scanf("%d", &num);
 for (int i = 0; i < num; i++)
 {
  int stack[60];
  char input[60];
  scanf("%s", input);
  for (int j = 0; j < strlen(input); j++)
  {
   if (input[j] == '(')
   {
    push(stack);
   }
   else if(n != -1)
   {
    pop(stack);
   }
   else
   {
    n--;
    break;
   }
  }
  if (n == -1)
  {
   puts("YES");
  }
  else
  {
   puts("NO");
   n = -1;
  }
 }


 return 0;
}

2018년 4월 19일 목요일

BOJ13236 Collatz Conjecture

문제 링크 : BOJ13236

문제 요약

함수 \( f(n) \)을 다음과 같이 정의하자
$${\displaystyle f(n)={\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}}\\3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$

모든 자연수 n에 대하여 \( f(f(f(...f(n)))) \) 이 항상 1이 되는 순간이 있는지가 콜라츠 추측이다. 아직 이 문제는 미해결 난제로 남아있다.

문제에선 n이 1이 되는 과정을 출력하면 된다.

문제 풀이

반복문을 통하여 변수를 계속 변화시키다가 1이 되는 시점이 오면 종료한다.

소스코드 (C++)

#include <iostream>
using namespace std;

int main()
{
    int n; cin >> n;
    
    while(n != 1)
    {
        cout << n << ' ';
        n = (n % 2 == 0) ? n/2 : 3*n+1;
    }
    
    cout << 1 << '\n';
    
    return 0;
}

소스코드 (Python2)

n = int(raw_input())

while n != 1:
    print n,
    if n % 2 == 0:
        n /= 2
    else:
        n = 3*n+1

print 1

소스코드 (아희)

삭밣밣밣붏
우더더더어    해
아방빵망빵반밧나타추
  오퍼 누번  우
콜  뫃 우추러번뻥
라추 뽀 우붇
츠측 포어어뚜
   도터벗벋