Learn: 7월 2018

2018년 7월 27일 금요일

백준 14891 톱니바퀴

톱니바퀴는 0번부터 3번까지 4개가 일렬로 있고, 0 - 1 - 2 - 3 이렇게 맞닿아(-) 있다.
한 톱니바퀴 당 톱니가 0번에서 7번까지 8개가 있는데, 맞닿아 있는 톱니는 2번과 6번이다.

0번이 돌아가면 1번이 돌아간다.
1번이 돌아가면 0번과 2번이 돌아간다.
2번이 돌아가면 1번과 3번이 돌아간다.
3번이 돌아가면 2번이 돌아간다.

어떤 톱니바퀴가 돌면, 자신의 양 옆 톱니바퀴가 영향을 받아 돌아가게 하되,
회전 횟수 한 번 당, check 배열을 사용해서 한 번 돈 것은 돌지 않는 식으로 처리하면 될 것 같다.

그리고 돌리기 전 2번, 6번 톱니를 비교해서 옆의 톱니바퀴에 영향을 줄지 말지를 결정해야 한다.

영향을 주는 것이 결정되면 배열에 들어가 있는 값을 이동시켜 돌려주면 될 것 같다.

2018년 7월 26일 목요일

백준 1475 방 번호

내 풀이의 핵심을 설명하자면,

9를 6대신 쓸 수 있고, 6을 9 대신 쓸 수 있으므로 6과 9를 같은 숫자로 보는 것이다.

같은 숫자로 보면 한 세트에 2개씩 있으므로 ~~(6의 개수 + 9의 개수) / 2 개만큼 필요할 것이다.~~ 이렇게 해서 다른 숫자들의 개수와 비교를 해서 최대값을 구하면 그 값이 필요한 세트의 개수의 최소값이 된다.

*** 그런데, (6의 개수 + 9의 개수) / 2 할 때, 정수 나눗셈이기 때문에 정확히는 (6의 개수 + 9의 개수 + 1) / 2 개 만큼 필요할 것이다.

그리고 나는 숫자로 입력받아서 10으로 나누면서 한 자리씩 취하는 방법을 이용했는데, 이 경우 0이 입력으로 들어오면 count를 하지 못하므로 ans = 1로 초기화 해두는 방법을 이용했다.

2018년 7월 25일 수요일

백준 15897 (UCPC 2018 예선 H번) 잘못 구현한 에라토스테네스의 체

이 문제는 UCPC 때는 3시간 내내 붙잡고 있다가 못 푼 문제인데... 결국 풀었다.
내가 푼 방법을 정리해 보고자 한다.

----------------------------------------------
1 int n;
2 cin >> n;
3 int* sieve = new int[n + 1];
4 for(int i = 1; i <= n; i++) {
5 for(int j = 1; j <= n; j += i) {
6 sieve[j] += 1;
7 }
8 }

----------------------------------------------

주어진 코드에서 6번째 줄이 입력으로 들어오는 n에 따라 몇 번 실행되는지를 구해야 하는 문제인데, 예를 들어 n이 4라고 하면
j = 1, 2, 3, 4
j = 1, 3
j = 1, 4
j = 4
이렇게 총 9번 실행된다.

바깥쪽 for문의 i 값에 따라 안쪽 for문의 실행횟수가 결정된다고 볼 수 있다.
안쪽 for문에서 j = 1부터 시작하여 i만큼 더하면 n이하일 때까지 반복하므로,
각 i마다 (n - 1) / i 만큼 안쪽 for문이 실행된다.

근데 n이 최대 10억까지 입력으로 들어오기 때문에... 일일이 다 더했다간 시간초과이다.
여러 방법을 고민해보다가 n / 2, n / 4정도까지 줄이기도 해봤었는데... 역시나 1초에 들어오기는 버겁다.

하지만 잘 생각해보면 O(루트n)만큼으로 줄일 수 있다.
내가 찾은 방법을 설명하기가 쉽지 않아서, 예를 들어서 설명해 보겠다.

n이 12인 경우를 예로 들어보면,
j = 1부터 시작하고, n번 모두 1부터 시작하므로 n번 도는 것은 무조건 확정이고,
거기에 (n - 1)을 i로 나눈 몫을 구해서 더해야 한다. 그런데, 모든 i에 대해 그 몫을 구할 필요가 없다.
숫자(a) 자신과 1만 약수로 갖는 소수를 구할 때에도 보면, 2부터 (a - 1)까지 다 나눠보고 나누어 떨어지는지(1과 자기 자신 외의 약수가 있는지)를 알아보는 방법도 있지만, 굳이 다 나누어 볼 필요 없이 (루트a) 까지만 나누어 보면된다.
12를 예로 들면
2 * 6 = 12
3 * 4 = 12
4 * 3 = 12
6 * 2 = 12
에서 볼 수 있듯이, 2, 3까지만 나누어 보면 4, 6으로 다 나누어 본 것과 같으므로...
(루트a)이하의 수로 나누면 (루트a)이상의 수로 나눠본 것과 같다는 것을 알 수 있다.

마찬가지로 이 문제에서도 똑같이는 아니지만 비슷한 개념을 적용해 볼 수 있다.
n = 12라고 하면, 먼저 1부터 시작하므로 변수 ans(답)에 12를 저장해둔다.
그리고 (n - 1)인 11을 1부터 11까지 나눈 몫을 다 더해주면 답이 되는데,

1 * 11
2 * 5
3 * 3
4 * 2
5 * 2
6 * 1
7 * 1
8 * 1
9 * 1
10 * 1
11 * 1

가 된다. 그래서 12 + 11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 41 이 답이다.

잘 보면 1 * 11 과 11 * 1, 2 * 5와 5 * 2, 가 짝을 이루고 있는 것을 볼 수 있는데,
x * x <= 11인 x = 3까지만 보면, 즉 1 * 11과 2 * 5를 보면 11 * 1과 5 * 2까지 해보지 않고
알 수 있다.

하지만, 좀 부족하다. 3 * 3은 당연히 짝이 없다해도, 4 * 2, 6 * 1, 7 * 1, ... 10 * 1 은 어떻게 예상할 수 있을까?
(루트n)까지 하는 것으로는 부족한 것이 아닐까? 다 해봐야 하지 않을까?

2 * 5로 5 * 2를 알 수 있다. 그런데 4 * 2를 알 수 있는 2 * 4는 왜 없을까? 4 * 2는 되는데 왜 2 * 4는 되지 않을까?

11 = 4 * 2 + 3 이지만 11 = 2 * 5 + 1이다. 즉 나누는 수가 2이냐 4이냐의 차이이다.
2로 나누면 나머지가 2보다 작아야 하기 때문에 몫이 크게 나온다. 4로 나누면 나머지가 4보다 작으면 되니까 몫이 2까지 나온다.

그럼 3 * 2는 어떨까? 3 * 2 + 5 = 11인데, 나머지 5가 3보다 크기 때문에 안된다.
4 * 2 + 3 = 11로 나머지 3이 4보다 작아서 가능한 것과 차이가 있다.

즉 2 * 5를 보면 5 * 2가 된다는 것은 바로 알 수 있지만, 4 * 2가 되는지, 3 * 2가 되는지는 판단하는 작업이 필요하다. 물론 이것을 일일이 확인하면 시간복잡도가 커진다.
위에서 보았듯이, x * 2가 가능하려면, n - x * 2 < x 가 되어야 한다.

여기서는 2이지만 이를 모든 경우에 적용하면
n - x * i < x 이어야 하고, 이를 정리하면, x > n / (i + 1) 이다.
즉, x * i가 가능한 x값의 하한값은 (n + i + 1) / (i + 1)이 되는 것이다.

lo = (n + i + 1) / (i + 1) 이라고 하면
lo값부터 (n - 1) / i 값까지 모두

lo * i
(lo + 1) * i
.
.
.
((n - 1) / i) * i

라는 것을 유추할 수 있는 것이니, ans += ((n - 1) / i - lo + 1) * i 를 해주면 된다.

단, 주의해야할 것은 3 * 3 같이 제곱 수들은 여러번 더해지면 안되는데, 한 번 더 더해진다.
그래서 (n - 1) / i 와 i값이 같을 때는 i만큼 빼줘야 한다.

자료형도 long long으로 하였고, 결국 이렇게 해서 AC를 받았다.

2018년 7월 21일 토요일

백준 10803 정사각형 만들기

엄청 어려워 보였는데, 생각해보니 간단할 것 같기도 하다.

문제 조건을 보면 한 번 짜르면 무조건 끝까지 잘라야 하고, 수평/ 수직으로만 자를 수 있기 때문에...

d[n][m] = n * m의 직사각형을 잘라서 얻을 수 있는 정사각형 조각의 최소 개수

로 놓고, 수평으로 자르는 경우, 수직으로 자르는 경우 1 ~ n, 1 ~ m 모든 경우를 다 보면서 그 중 최소값을 얻어내면 될 것 같고,

최소값을 구해야 하므로 n == m인 경우 더 자를 필요 없이 1을 리턴해주는 식으로 구현하면 될 것 같다.

그런데, 생각해보니 그렇게 하면 시간 복잡도가 n * m * (n + m)이 될 것 같은데...

100억 정도가 되어 너무 크다. 그런데 생각해보면 n + m부분에서 n + m을 다 해볼 필요 없이, 그러니까 1 ~ n, 1 ~ m을 다 볼 필요 없이 절반까지만 보면 될 것 같다. 어차피 절반 이후로는 똑같으니까...

음... 그래도 여전히 시간복잡도가 크다. 그런데 위와 같이 절반까지만 보기 때문에 재귀로 구현하면 d[n][m]에 해당하는 n * m부분이 정말 n * m만큼 호출될 것 같지는 않다.... 일단 구현해 봐야겠다.

제출했더니 역시나 시간초과가 떴다...

어떻게 줄여야할까?

음 일단 생각나는 것이... d[w][h] 나 d[h][w]나 같다는 것이다. 이것을 한 번 적용해 봐야겠다. 그러면 또 반 정도 줄일 수 있을 거 같긴하다.

음 그런데, 저것을 적용하니 좀 답이 잘못 나온다.(10000, 100인 경우에...)

왜 그런지 이유는 잘 모르겠지만... -> 생각해보니 애초에 dp배열크기가 d[10001][101]이라 그런 것 같다. w와 h의 범위가 다르다... 그래서 배열 범위를 초과하여 잘못된 값이 들어간 것 같다.

일단 또 생각해본 것이 w나 h 둘 중 하나가 1인 경우 굳이 더 나눠 볼 필요가 없다는 것이다. 일단 이 부분을 추가해도 시간이 그리 단축되지는 않는다.

확실하지는 않은데, w와 h의 gcd(최대공약수)값부터 자르거나 최대공약수 단위로 자르는 건 어떨까? 최대공약수가 1이면 1부터 해야겠지만, 최대공약수가 2이기만 해도 엄청 많이 줄일 수 있을 것 같은데...

확실하게 증명은 할 수 없지만... 일단 최대공약수부터 시작해서 최대공약수 단위로 자르는 식으로 구현해 봐야겠다.

일단 예제에 대해서는 제대로 나오기는 하는데, 시간초과를 받았다... 9999 100 같은 케이스에 대해서는 여전히 느리다.

2018년 7월 20일 금요일

백준 15685 드래곤 커브

일단 규칙을 좀 생각해봤다.

1. k세대는 (k - 1)세대를 시계방향으로 90도 돌린 후에 (k - 1)세대의 끝점에 90도 돌린 것의 끝점을 붙이게 된다. 그래서 (k - 1)세대의 역방향으로 새로운 길이 추가된다고 볼 수 있다.
역방향은 x, y방향은 각각 유지하면서 부호만 바꿔주면 된다.

2. 그리고 시계방향으로 90도 돌릴 경우 각 이동 규칙은...
y방향 음수 -> x방향 양수
y방향 양수 -> x방향 음수

x방향 음수 -> y방향 음수
x방향 양수 -> y방향 양수

일단 x -> y, y -> x 가 되고, y방향의 경우만 부호가 바뀐다.
(x, y) -> (-y, x) 로 해주면 된다.

규칙 1과 2를 이용해서 점을 찍고나서
모든 점을 돌면서 각 점마다 오른쪽, 아래 방향으로 1 * 1 정사각형을 구성하는 꼭지점이 있는지 확인해 보면서 1 * 1 정사각형의 개수를 세면될 것 같다.

규칙 1과 2를 이용해서 점을 찍는 부분의 구현이 좀 까다롭다.
먼저 k세대를 구하기 위해서 0세대부터 시작을 한다.
i세대의 이동 방향을 reverse해주고, 그 값을 90도 돌려주는 작업을 해준다.
그리고 i세대의 끝에 이어 붙인다. 그러면 (i+1)세대의 이동방향이 완성된다. 각 이동 방향은 pair(x, y)로 묶어서 vector에 이어붙일 것이다.

이렇게 k세대의 이동방향을 구하면 그를 토대로 점을 check해준다.

결국 이렇게 구현해서 AC를 받았다.
코드가 꽤 길어졌는데, 맞은 사람을 보니 짧게 구현한 사람도 꽤 있다. 이해는 잘 안 가지만, 좀 더 간단히 구현할 수 있는 방법이 있는 것 같다... 더 열심히 해야겠다.

백준 1005 ACM Craft

먼저 주어진 건설 순서를 이용해서 그래프를 만들고, 지어야 할 건물 W부터 시작해서 거꾸로 탐색하는 방식으로 dp로 구현해 볼 생각이다.

거꾸로 탐색하면서 건물 W를 짓기 전에 지어야 할 각 건물까지의 시간 중 최대값을 선택하는 방식으로 하면 될 것 같다. 그리고 이미 탐색한 부분은 메모이제이션을 통해 더 탐색하지 않도록 한다.

위상정렬 문제를 예전에 푼 것을 좀 찾아봐서 다시 풀어봐야겠다.
이 문제는 그냥 그래프 + dp처럼 풀어서 AC를 받았는데, 예전에 풀었던 문제 중에 경로까지 출력해야 하는 문제가 있어서 좀 까다로웠던 것 같고 위상정렬을 풀기 위한 방식이 있었는데... 기억이 잘 안난다. 찾아서 풀어보자!

2018년 7월 19일 목요일

CS Academy Round 84 Three ones

koosaga님이 출제하신다고 슬랙에 홍보해 주셔서 CS Academy를 처음 알게되었고, round 84에 참여해 봤는데, 일단 한 문제밖에 못 풀었다...

그 외 다른 문제는 읽지도 못했고, Three ones문제는 좀 고민을 했는데...
일단 상세한 풀이는 없지만 소스코드가 있어서 여기 기록해 둔다. 생각해보고 내가 풀이를 정리해 봐야겠다.

문제
https://csacademy.com/contest/round-84/task/three-ones/

풀이
https://csacademy.com/contest/round-84/analysis/

STL queue에서 pop에 리턴값이 없는 이유

백준 슬랙에서 누군가 왜 STL queue에서 pop을 쓰면 pop만되고, pop된 값이 리턴되지 않는지 질문했는데, 그에 대한 답으로 아래의 링크를 올려주셨다.

https://stackoverflow.com/questions/25035691/why-doesnt-stdqueuepop-return-value

읽어봤는데, 영어라 확실히 이해한 것 같지는 않지만...
내가 이해한 것을 정리해보면,

"pop을 쓸 때, queue에 있는 해당 값을 제거하게 되기 때문에 해당 값을 리턴해주기 위해서는 해당 값의 참조값(주소값)을 이용해 리턴해줄 수 없고, 따로 값을 저장하고 리턴해야 하는 return by value를 사용해야 하고 이는 비효율적이다. "
라는 의견도 있었고,

하지만 진짜 이유는... 만약 해당 값을 리턴하게 된다면, 리턴하기 전에 해당 엘리먼트를 지워야하기 때문에, 이미 어디에도 존재하지 않는 값을 리턴하는 것이라... exception으로부터 안전하지 못하기 때문에... exception safety를 위해서라고 한다.

사실 정확히 이해는 안 되었지만, exception부분은 C++과 STL에 대해서 좀 공부를 해야 이해할 수 있을 것 같다. C++에 대해서 공부해보고 다시 생각해 봐야겠다.

백준 2091 동전

이 문제는 꽤 오래전부터 못 풀던 문제인데, 인터넷에 검색해서 공식 사이트의 풀이를 찾았다.

물론 코드만 있어서 좀 분석이 필요하다. 시간이 좀 걸릴 것 같지만 틈틈이 계속 봐야겠다.

https://contest.felk.cvut.cz/03prg/solved/change.c

/*
 * Solution to Charlie's change task
 */
#include <stdio.h>

const int p[4] = {1,5,10,25};

#define MIN(a,b) ((a) < (b) ? (a) : (b))

int compute(int *c, int *use, int start, int price)
{
 int i, val;

 val = 0;
 for (i = 0; i <= start; i++)
  val += c[i]*p[i];
 for (i = start; i >= 0; i--) {
  val -= p[i]*c[i];
  if (val > price)
       use[i] = 0;
  else
       use[i] = (price-val+p[i]-1)/p[i];
  if (use[i] > c[i] || use[i]*p[i] > price)
       return -1;
  price -= use[i]*p[i];
 }
 val = 0;
 for (i = 0; i < 4; i++)
     val += use[i];
 return val;
}

int main(void)
{
 int price, c[4], val, use[2][4], i, coins[2];

 while (1) {
      scanf("%d %d %d %d %d", &price, &c[0], &c[1], &c[2], &c[3]);
  if (!price && !c[0] && !c[1] && !c[2] && !c[3])
   break;

  val = 0;
  for (i = 0; i < 3; i++)
       val += c[i]*p[i];
  if (val > price)
       use[0][3] = 0;
  else
       use[0][3] = MIN((price-val+p[3]-1)/p[3], c[3]);
  coins[0] = compute(c, use[0], 2, price - use[0][3]*p[3]);
  if (use[0][3] < c[3]) {
   use[1][3] = use[0][3]+1;
   coins[1] = compute(c, use[1], 2, price - use[1][3]*p[3]);
  }
  else
       coins[1] = -1;
  if (coins[0] == -1 && coins[1] == -1)
       puts("Charlie cannot buy coffee.");
  else {
       i = 0;
       if (coins[1] > coins[0])
        i = 1;
   printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", use[i][0], use[i][1], use[i][2], use[i][3]);
  }
 }
 return 0;
}

백준 2751 수 정렬하기 2

이 문제를 풀 때 두 가지 방법으로 풀어보았다.

1. C++ STL의 sort사용
2. bucket sort 사용

시간 복잡도는 각각 O(NlogN), O(N)으로 차이가 많이 나지만,
실제 백준 온라인 저지에 제출했을 때, 8ms정도 밖에 차이가 나지 않는다. 왜 그럴까?

일단 스타트링크 오프라인 강의 질문 사이트를 통해 백준님께 질문을 남겼다.

백준 11004 k번째 수 구현 관련...

일단 cin, cout을 쓸 때, ios_base::sync_with_stdio(false); 를 써주지 않으면 시간초과를 받을 수 있다.

그리고 이전과 달리 STL sort를 사용해도 통과하느 것으로 보인다.

아무튼 quick sort를 응요한 quick selection을 이용해서 구현했는데...
맨 왼쪽 수를 pivot으로 정하고, pivot의 위치를 찾아내는 partition함수의 구현에서,

코드 1)-------------------------------------------------------------------------------------------
int partition(int left, int right) {
int pivot = left;
int lo = left + 1, hi = right;

while(lo < hi) {
while(arr[lo] <= arr[pivot] && lo <= right) lo++;

while(arr[hi] >= arr[pivot] && hi >= left + 1) hi--;

if(lo < hi) swapArr(lo, hi);
}

swapArr(hi, pivot);

return hi;
}
---------------------------------------------------------------------------------------------------
위의 코드와 같이 구현했다가, 틀렸는데 ,

아래 코드 2) 와 같이 구현하면

코드 2)-------------------------------------------------------------------------------------------
int partition(int left, int right) {
int pivot = left;
int lo = left + 1, hi = right;

while(lo <= hi) {
while(arr[lo] <= arr[pivot] && lo <= right) lo++;

while(arr[hi] >= arr[pivot] && hi >= left + 1) hi--;

if(lo < hi) swapArr(lo, hi);
}

swapArr(hi, pivot);

return hi;
}
---------------------------------------------------------------------------------------------------
맞았습니다를 받을 수 있다.

달라진 점은 while(lo < hi) -> while(lo <= hi) 이다. 사실 처음에는 lo 와 hi가 같아질 일도 없고, 설령 같아지더라도 그 때 while문을 나오는 것이 문제될 일은 없다고 생각했다. 그런데 잘 생각해보니 길이가 2인 수열이 있으면 lo와 hi가 2로 같아져 아예 while문 안으로 들어갈 수 없게되는 문제가 있다.

그렇게 되면 예를 들어 {1, 2}라는 수열이 있을 때 hi값은 2가되어 while문 안에 못 들어가고, swapArr(hi, pivot)을 거쳐 {2, 1}로 수열을 변경하게 되어 잚못된 답이 나오게 된다.

2018년 7월 17일 화요일

ios_base::sync_with_stdio(false)

cin, cout을 빠르게 쓰려고 ios_base::sync_with_stdio(false)을 main함수 위쪽에 썼는데, 컴파일 과정에서 에러가 나서 main함수 안에 넣어주었고, 그렇게 하니 에러가 나지 않았다.

추가) < 10989 수 정렬하기 3 >을 풀면서 cin, cout도 써보고 scanf, printf도 써보면서 테스트해 봤는데, ios_base::sync_with_stdio(false)를 써주면 그냥 scanf, printf을 사용했을 때 보다 cin, cout을 사용했을 때, 더 빠른 것을 알 수 있었다.

백준 10814 나이순 정렬

나이와 가입 순서를 가지고 sorting하여 문제를 풀었는데, 과거에 내가 푼 방법을 보니 꽤 괜찮은 방법이 있어 여기에 기록한다.

나이가 1 ~ 200이므로 크기 201의 vector<string>배열을 만든다.
나이를 입력 받으면 radix sort(bucket sort)처럼 나이를 vector배열의 index로 사용하여 vector배열에 이름(string)을 저정한다.

나이 순으로 정렬하고, 나이가 같으면 가입순서대로 정렬해야 하는데, 일단 나이를 배열의 index로 사용했으므로 1부터 200까지 보면 나이순으로는 정렬이 되어 있고, 각 나이에 해당되는 배열에 가입한 순서대로 string이 저장되어 있으므로 따로 가입 순서에 따라 정렬할 필요도 없다.

그냥 배열의 순서대로 배열 내 저장된 순서대로 출력하면 정답이 된다.

2018년 7월 11일 수요일

#define의 속도에 대해...

https://algospot.com/forum/read/3568/

위의 링크와 캡쳐에서 볼 수 있듯이, #define을 쓰면 함수가 여러번 호출될 수 있어 더 느려질 수 있다.

그리고 전처리기 등...에 대해 공부할 필요가 있다. CS공부하자...!

2018년 7월 9일 월요일

백준 2225 합분해

거의 같은 로직의 코드를 제출했는데 속도가 12ms, 32ms로 매우 다르게 나와서 무슨 차이인가 하고 봤더니... MOD값을 const로 선언했냐 안 했냐의 차이였다..

const로 선언해주니 무려 20ms나 줄어들었다.

for문 안에서 매번 modular 연산을 해주는데

const로 선언하면 상수처럼 되어 속도가 좀 더 빨라지나보다... 나중에 그 이유에 대해 좀 더 자세히 알아보자.

2018년 7월 8일 일요일

백준 2133 비트연산 사용해서 풀어보기...

백준 2156 포도주 시식

d[i][x] = i번째 잔부터 연속 x잔을 마실 때, 최대로 마실 수 있는 포도주의 양

d[i][0] = max(d[i + 1][1], d[i + 1][2])
d[i][1] = d[i + 1][0] + wine[i]
d[i][2] = d[i + 2][0] + wine[i] + wine[i + 1]

이렇게 풀었는데, 틀렸다...
감사하게도 질문게시판에 반례를 올려주신 분이 있었다.
https://www.acmicpc.net/board/view/21703#comment-37134
8
7 7 0 5 7 7 0 3

~~d[i][0] = max(d[i + 1][1], d[i + 1][2])~~ -> 이 부분이 문제였다.
나는 i번째 포도주를 안 마시기로 했으면, 그 다음 포도주는 무조건 마셔야 최대값이 된다고 생각했는데, 이 것은 맨 앞인 경우만 해당된다. 맨 앞의 2개의 잔을 모두 안 마시면 최대가 아니기 때문에(맨 앞의 1개의 잔을 마시면 그게 더 크므로) 이렇게 생각했었는데, 중간 부분에서는 가운데 2개가 비어야 최대가 될 수 있는 경우도 있다.

예를 들면, o o x x o o 인 경우... 가운데 x x중 하나를 선택하게 되면 3잔 연속이 되니까, o를 하나 포기해야 한다. 이 때, x에 있는 값이 o에 있는 값보다 작으면 최대가 될 수 없다. 그래서 최대가 되기 위해 x x -> 이 부분을 선택하지 않아야 할 수 있다.

그래서
~~d[i][0] = max(d[i + 1][1], d[i + 1][2])~~
-> d[i][0] = max(d[i + 1][0], max(d[i + 1][1], d[i + 1][2])) 으로 수정하였고, AC를 받았다.

2018년 7월 6일 금요일

백준 1463 1로 만들기

일단 3으로, 2로 모두 나누어 떨어지면 3으로 나누는 것이 최소값을 구할 수 있는 방법일까? 2로 나눠야 최소값이 나오는 경우도 있지 않을까?

그리고 3으로 나누어 떨어지는 홀수를 3으로 바로 안 나누고 1을 뺀 후에 2로 나누는 경우가 3으로 바로 나누는 경우보다 나을 수도 있지 않을까?

위의 사항들에 대해서... 확실하게 어떤 것이 최적이다라고 증명을 할 수 있으려나...
일단 증명을 안 한다면 모든 경우를 다 해보는 방식으로 dp를 적용해서 풀어도 된다.

-------------------------------------------------------

1. x가 3으로 나누어 떨어지면 3으로 나눈다.
2. x가 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다.

d[n] = 정수 n에 세가지의 연산을 적절히 사용해서 1을 만들기 위해 연산을 사용하는 횟수의 최소값.

d[n] = min(d[n / 3], d[n / 2], d[n - 1]) + 1;

2018년 7월 5일 목요일

10820 문자열 분석, fgets 주의사항

fgets로 받는 경우 입력 문자열의 최대길이가 100이므로 개행('\n')과 NULL값까지 고려해서 char 배열을 102로 잡아줘야 한다. str[102]

그런데 틀려서 보니...
fgets(str, 100, stdin)에서... fgets를 쓰면 개행('\n')까지 받기 때문에, 최대 100자까지가 아닌 101자까지 받도록 해야 한다...
fgets(str, 101, stdin);

아 그런데 또 틀렸다...
직접 테스트 해보니.. fgets(str, 11, stdin)으로 할 경우 10글자까지만 저장된다. 개행('\n')도 저장되지 않고 딱 10글자만 저장된다. (개행까지 저장되려면 9글자를 입력해야 한다.)
결국 저 11이라는 숫자는 문자열의 NULL값까지 포함한 길이인 것 같다.
그렇기 때문에 fgets(str, 102, stdin)으로 해줘야 통과할 수 있을 것 같다.
그렇게 고쳐서 제출했더니 AC를 받았다....

2018년 7월 2일 월요일

백준 1008 A/B

https://www.acmicpc.net/board/view/2432

정답과의 차이가 1e-9이하이면 정답인 문제
출력되는 소수의 범위를 늘려야 한다.

float로 하면 6자리정도까지만 정확하기 때문에 틀리게 된다.
double(%lf)를 이용해야 한다.

백준 1002 터렛

주의사항

(x1, y1)과 (x2, y2)가 같은 경우도 생각해야 함!
원 하나가 다른 원 하나를 포함하는 경우도 생각해야 함. 포함하여 접점이 1개일 수도 있고, 포함해서 접점이 없을 수도 있다.

근데 이 모든 것을 간단하게 처리하는 방법도 있다.

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void) {
int t;
scanf("%d", &t);
while(t--) {
double x1, y1, x2, y2;
double dist[3];
scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &dist[0], &x2, &y2, &dist[1]);
dist[2]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
sort(dist, dist+3);
if(dist[0]==0 && dist[1]==dist[2]) {
printf("-1\n");
}
else if(dist[2]>dist[1]+dist[0]) {
printf("0\n");
}
else if(dist[2]==dist[1]+dist[0]) {
printf("1\n");
}
else {
printf("2\n");
}
}
return 0;
}