S. Kevin 창고

[BOJ] 1149번. RGB거리

프로그래밍/알고리즘2017. 12. 19. 23:57

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


문제는 링크 참고.


풀이.


dy[i][j] : i번째집이 j번째 색으로 칠했을 때 들 수 있는 가장 적은 비용

dy[i][j] = dy[i][j] + MIN(dy[i][(j + 1) % 3], dy[i][(j + 2) % 3]);


여기서 R은 0, G는 1, B는 2로 했다.


입력 예제 설명.


입력예제 : 

3
26 40 83
49 60 57
13 89 99


0번째 집이 색칠 하는 경우

R : 26

G : 40

B : 83


1번째 집이 색칠 하는 경우

R : 49 + MIN(0번째 집 G를 칠 했을 때 비용, 0번째 집 B를 칠 했을 때 비용)

G : 60 + MIN(0번째 집 R를 칠 했을 때 비용, 0번째 집 B를 칠 했을 때 비용)

B : 57 + MIN(0번째 집 R를 칠 했을 때 비용, 0번째 집 G를 칠 했을 때 비용)


2번째 집이 색칠 하는 경우

R : 13 + MIN(1번째 집 G를 칠 했을 때 비용, 1번째 집 B를 칠 했을 때 비용)

G : 89 + MIN(1번째 집 R를 칠 했을 때 비용, 1번째 집 B를 칠 했을 때 비용)

B : 99 + MIN(1번째 집 R를 칠 했을 때 비용, 1번째 집 G를 칠 했을 때 비용)


마지막 집에서의 값 중 MIN 값을 구하면 색칠할 때 최소로 드는 비용을 구할 수 있다.



'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1032번. 명령 프롬프트  (0) 2017.12.19
[BOJ] 1015번. 수열 정렬  (0) 2017.12.18
[BOJ] 1013번. Contact  (0) 2017.12.07
[BOJ] 1012번. 유기농 배추  (0) 2017.12.04
[BOJ] 1010번. 다리 놓기  (0) 2017.11.27

[BOJ] 1032번. 명령 프롬프트

프로그래밍/알고리즘2017. 12. 19. 23:25

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


문제는 링크 참고.


풀이.

풀이가 필요한가? ㅋㅋ


문자열의 최대 길이가 50이기 때문에 그냥 생각 안하고, 머리에서 생각나는 대로 풀었다.


입력된 문자열 중, 문자열이 같은 부분만 찾아서 출력하고 나머지 부분은 '?'로 출력하면 된다.



'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1149번. RGB거리  (0) 2017.12.19
[BOJ] 1015번. 수열 정렬  (0) 2017.12.18
[BOJ] 1013번. Contact  (0) 2017.12.07
[BOJ] 1012번. 유기농 배추  (0) 2017.12.04
[BOJ] 1010번. 다리 놓기  (0) 2017.11.27

[BOJ] 1015번. 수열 정렬

프로그래밍/알고리즘2017. 12. 18. 23:44

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


문제는 링크 참고.


풀이.


문제에 나와 있듯이 "B[P[i]] = A[i]" 식을 이용해서 풀면된다.


입력예제 "2 3 1" 에서 출력예제 "1 2 0" 이 나오는 이유는


A { 2 3 1 }

P { 1 2 0 }        이 있다면


B[P[0]] = A[0] = B[1] = 2

B[P[1]] = A[1] = B[2] = 3

B[P[2]] = A[2] = B[0] = 1


결과적으로 B { 2 3 1 }이 완성되고, B는 A로부터 정렬된 수열이란 것을 알 수 있다.



위 방법보다 더 쉬운 방법도 있다.

숫자를 입력받을 때 각 숫자에 카운팅을 매겨, 순위를 구해서 답을 구한다.


다른 사람 소스보고 알았다 ㅋㅋ

왜 이런 방법을 생각을 못 했을까..




'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1149번. RGB거리  (0) 2017.12.19
[BOJ] 1032번. 명령 프롬프트  (0) 2017.12.19
[BOJ] 1013번. Contact  (0) 2017.12.07
[BOJ] 1012번. 유기농 배추  (0) 2017.12.04
[BOJ] 1010번. 다리 놓기  (0) 2017.11.27

[BOJ] 1013번. Contact

프로그래밍/알고리즘2017. 12. 7. 23:27

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


문제는 링크 참고.




풀이.


이 문제는 각 문자마다 다음에 뭐가 올 수 있는지를 분석하여서도 풀 수 있다.


하지만 다음과 같이 그래프를 그려 각 문자를 검사하는 상황마다 인덱스를 매겨서 쉽게 풀 수도 있다.



(100+1+ | 01)+


패턴에 맞는 문자열을 위 그래프를 따라가면서 검사해보면 이 그래프가 왜 그려졌는지 쉽게 알 수 있다.


여기서 빨간색 원은 마지막으로 문자열을 검색했을 때 상태가 0번,4번,5번일 경우 맞는 문자열의 상태의 번호를 표시한다.


ex1)

문자열 : 10011001 은 상태가 0→1→2→3→4→5→6→3→4 로 끝나므로, 맞는 문자열이다.


ex2)

문자열 : 101101 은 상태가 0→1→2→8(정의되지 않은 상태) 이므로, 틀린 문자열이다.


위의 그래프를 테이블로 만들어서 str을 검사하면서 돌리면 된다.







'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1032번. 명령 프롬프트  (0) 2017.12.19
[BOJ] 1015번. 수열 정렬  (0) 2017.12.18
[BOJ] 1012번. 유기농 배추  (0) 2017.12.04
[BOJ] 1010번. 다리 놓기  (0) 2017.11.27
[BOJ] 1463번. 1로 만들기  (0) 2017.11.26

[BOJ] 1012번. 유기농 배추

프로그래밍/알고리즘2017. 12. 4. 22:20

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


문제는 링크 참고.



풀이.


이 문제는 딱 보고 생각나는 데로 풀면된다.


배추가 있는 부분을 찾아 그 부분의 갯수를 세어 출력하면 배추 흰 애벌레가 얼마나 필요한지 알 수 있다.


입력된 좌표를 돌면서 1을 찾았을 때, 그 부분의 1을 DFS를 이용하여 다 없애버리고 cnt ++을 하면된다.


여기서 시간을 좀 더 빠르게 하고 싶다면 입력된 좌표 갯수 만큼만 탐색을 하여 부분을 찾으면 조금 더 시간이 빨라질 수 있다.

(우리가 인지할 만큼 빨라지지 않음)



참고사항.

백준에서 푸는데 49번 째 줄을 printf("%d", cnt);로 하고 제출을 하니 답이 틀렸다고 나온다.

앞으로는 출력할 때 개행열(\n)을 붙히는 습관을 들이자.

'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1015번. 수열 정렬  (0) 2017.12.18
[BOJ] 1013번. Contact  (0) 2017.12.07
[BOJ] 1010번. 다리 놓기  (0) 2017.11.27
[BOJ] 1463번. 1로 만들기  (0) 2017.11.26
[BOJ] 1008번. 분산처리  (0) 2017.11.24

[BOJ] 1010번. 다리 놓기

프로그래밍/알고리즘2017. 11. 27. 23:15

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


문제는 링크 참고.



풀이.

N = 서쪽의 사이트 갯수, M = 동쪽의 사이트 갯수


N = 2, M = 4일 때를 가정해보자


N(1)번 사이트와 M(1)번 사이트를 연결하면 남는 사이트들은 서쪽 사이트 1개 동쪽 사이트 3개가 남는다.

즉, N(1)번과 M(1)번을 연결하면 N = 1, M = 3 일 때의 가짓수가 나온다는 것이다.


그렇다면 마찬가지로 N(1)번과 M(2)번 사이트를 연결하면 남는 사이트들은 서쪽 사이트 1개 동쪽 사이트 2개가 남는다.

이것 또한 N(1)번과 M(2)번 사이트를 연결하면 N = 1, M = 2개의 가짓수가 나온다는 것이다.


이렇게 각 사이트마다 연결하여 가짓수를 구하면


(N = 1, M = 3 가짓수) + (N = 1, M = 2 가짓수) + (N = 1, M = 1 가짓수) = (N = 2, M = 4 가짓수)


이라는 식이 완석된다.


자 그렇다면 N = 2, M = 3일 때를 가정해보자


위에서 했던 것과 마찬가지로 식을 구하면


(N = 1, M = 2 가짓수) + (N = 1, M = 1 가짓수) = (N = 2, M = 3 가짓수) 가 된다.




자 여기까지 구하면, 위의 첫번째 식(N = 2, M = 4 가짓수)을 두번째 식(N = 2, M = 3 가짓수)를 통해 줄일 수 있게된다.


(N = 1, M = 3 가짓수) + { (N = 1, M = 2 가짓수) + (N = 1, M = 1 가짓수) } = (N = 2, M = 4 가짓수)


위 식에서 중괄호("{ }")로 묶은 값은 (N = 2, M = 3 가짓수)와 같은 값이므로 다음과 같이 식을 바꿀 수 있다.


(N = 1, M = 3 가짓수) + { (N = 2, M = 3 가짓수) } = (N = 2, M = 4 가짓수)


그러므로 점화식은


D[i][j] : 서쪽 사이트 i개와 동쪽 사이트 j개로 다리를 교차하지 않고 이을 수 있는 경우의 수

D[i][j] = D[i - 1][j - 1] + D[i][j - 1];


이된다.





'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1013번. Contact  (0) 2017.12.07
[BOJ] 1012번. 유기농 배추  (0) 2017.12.04
[BOJ] 1463번. 1로 만들기  (0) 2017.11.26
[BOJ] 1008번. 분산처리  (0) 2017.11.24
[BOJ] 1007번. Vector Matching  (0) 2017.11.22

[BOJ] 1463번. 1로 만들기

프로그래밍/알고리즘2017. 11. 26. 23:57

사지방 시간이 없어서 급하게 올림.



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


풀이:


숫자 10을 1로 만들 때, 10 9 3 1 이렇게 만들어진다.

D[i] : 숫자 i를 1로 만들 수 있는 최소 연산 횟수.


D[i] = MIN(D[i / 2], D[i / 3], D[i - 1]) + 1


단, D[i / 2], D[i / 3]은 i가 2로 나누어지거나, i가 3으로 나누어질 때만 참조 가능.


**** 주의. 나눌 수 있다고 해서 나눈 값으로 참조하면 최소값이 되지 않는다.

ex) 

  10 -> 9 -> 3 -> 1 과 10 -> 5 -> 4 -> 3 -> 1 중, 전자가 답이다.



'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1012번. 유기농 배추  (0) 2017.12.04
[BOJ] 1010번. 다리 놓기  (0) 2017.11.27
[BOJ] 1008번. 분산처리  (0) 2017.11.24
[BOJ] 1007번. Vector Matching  (0) 2017.11.22
프로그램 명: suffix_array(open)  (0) 2012.06.22

[BOJ] 1008번. 분산처리

프로그래밍/알고리즘2017. 11. 24. 23:39

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


문제명

분산처리

설 명

문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.


입력 예시

5

1 6

3 7

6 2

7 100

9 635


출력 예시

1

7

6

1

9


이번 문제 풀면서 한 실수.

1. 자료형을 숫자크기를 고려하여 사용해야했는데 그렇게 안해서 시간 허비.

고칠 점

1. 프로그램 진행 중 발생될 숫자를 고려하여 자료형 사용하기.

2. 코드가 깨끗하지 않음. 다음부터 좀 정리해보기

느낀 점.

1. 작은 실수 때문에 시간 허비하니까 너무 짜증난다. 

문제 힌트.

http://blog.naver.com/turewww/220700077878


이 블로그에 나와있는 것을 보면 바로 문제 풀 수 있다.


딱히 안봐도, 머리만 조금 굴려도 풀수 있다.


힌트 끝.


'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1010번. 다리 놓기  (0) 2017.11.27
[BOJ] 1463번. 1로 만들기  (0) 2017.11.26
[BOJ] 1007번. Vector Matching  (0) 2017.11.22
프로그램 명: suffix_array(open)  (0) 2012.06.22
[Finite Automata, computational geometry] 내부점 판별 (in_out)  (0) 2012.01.16

[BOJ] 1007번. Vector Matching

프로그래밍/알고리즘2017. 11. 22. 23:49

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


문제명

Vector Matching

설 명

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 Vector Matching은 벡터의 집합인데, 모든 벡터는 집합 P 중 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터들의 집합이다. 또, P속의 모든 점은 모두 단 한번만 쓰여야 한다.

 

V에 있는 벡터의 개수는 P에 있는 점의 절반이다.

 

평면 상의 점이 주어졌을 때, 집합 P의 Vector Matching에 있는 벡터들의 합의 길이의 최소값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

 

첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력

각 테스트 케이스 마다 소수점 7자리에서 반올림하여 정답을 출력한다. (구한 답이 0이어도 0.000000 을 출력해야 한다.)


입력 예시

2

4

5 5

5 -5

-5 5

-5 -5

2

-100000 -100000

100000 100000


출력 예시

0.000000

282842.712475


이번 문제 풀면서 한 실수.

1. 문제 제대로 읽지 않아서 소수점 7자리까지 출력해서 계속 오답이 출력된 것.

2. dfs 함수 재귀타고 들어갈 때, 올바르지 않은 인자값을 넣어준 것.

   dfs(vec + arVec[i], pos + 1, cnt + 1); → dfs(vec + arVec[i], i + 1, cnt + 1); 로 수정.

고칠 점

1. 최근 숙지한 Class, 동적할당을 활용하는 것은 좋았으나, 원래 짜던대로 그냥 동적할당이 아닌, 그냥 정적으로 사이즈를 정해놓고 짯으면 코드량이 줄어 더 빨리 짤 수도 있었을 듯. 다음부터 이런 문제는 그냥 정적으로 짜도 상관 없을 듯.

느낀 점.

1. 사지방에서 Dev C++을 이용해서 문제푸는데, 디버깅도 안되서 머리를 많이 굴리면서 했던거 같다. 이렇게 계속 풀다보면 도움이 될 것 같다.

2. 이번에 깃허브 사용해서 올려볼까 했는데 사지방에서는 깃허브가 접속이 안된다고 한다ㅠ

문제 힌트.

그림과 같이 벡터 A - B는 벡터 A와 B 사이에 있는 벡터와 같다.


서로 다른 점 P1과 P2가 있다고 하자. P1에서 P2로 가는 벡터를 위의 방식으로 구하면


Vector (P0 to P1 ) - Vector (P0 to P2) = Vector (P1 to P2)


위와 같은 식이 완성된다. 여기서 Vector (P0 to P1)은 P1의 좌표값과 같으므로 다음과 같이 작성할 수 있다.


P1 - P2 = Vector (P1 to P2)


[사진출처]

http://www.kshitij-iitjee.com/Adding-Vectors-Subtracting-Vectors-equality-of-vectors


힌트 끝.


'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1463번. 1로 만들기  (0) 2017.11.26
[BOJ] 1008번. 분산처리  (0) 2017.11.24
프로그램 명: suffix_array(open)  (0) 2012.06.22
[Finite Automata, computational geometry] 내부점 판별 (in_out)  (0) 2012.01.16
[더블릿] KnapSack  (0) 2012.01.06

프로그램 명: suffix_array(open)

프로그래밍/알고리즘2012. 6. 22. 21:35

프로그램 명: suffix_array(open)
제한시간: 1 초

문자열 dovelet 이 주어질 때

0123456
dovelet

이 문자열로 만들 수 있는 접미사는 7 개 이다.

  • dovelet(0)
  • ovelet(1)
  • velet(2)
  • elet(3)
  • let(4)
  • et(5)
  • t(6)
이 접미사 배열(suffix array)을 정렬하면
  • dovelet(0)
  • elet(3)
  • et(5)
  • let(4)
  • ovelet(1)
  • t(6)
  • velet(2)

입력

입력은 2000 이하의 문자열이 주어진다.

출력

정렬한 접미사 배열을 출력한다. 문자열과 수 사이에는 한 칸의 공백을 둔다.

입출력 예

입력

dovelet

출력

dovelet 0
elet 3
et 5
let 4
ovelet 1
t 6
velet 2



'프로그래밍 > 알고리즘' 카테고리의 다른 글

[BOJ] 1008번. 분산처리  (0) 2017.11.24
[BOJ] 1007번. Vector Matching  (0) 2017.11.22
[Finite Automata, computational geometry] 내부점 판별 (in_out)  (0) 2012.01.16
[더블릿] KnapSack  (0) 2012.01.06
[더블릿] 행오버  (0) 2012.01.04

티스토리툴바