2019. 8. 7. 18:50
728x90

Maximum path sum I

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

최상단 시작 지점에서 가장 아래층까지 내려가면서 거치는 경로 중 값의 합이 가장 큰 값은 몇인가.

목적지가 어디가 될지 알 수 없으므로 목적이 후보에서부터 출발지로 거슬러 올라가는 방식으로 구해야 한다. i + 1의 값과 i의 값을 합하여 합계가 큰 쪽은 남겨두는 방식으로 출발지점까지 거슬러 올라가면 합계가 가장 큰 값을 빠르게 구할 수 있다.
설명으로 나온 숫자 배열을 예로 들면 아래와 같이 진행된다.

이와 같은 방식으로 진행하면 결과 값을 빠르게 얻을 수 있다.



728x90

'공부 > 문제풀기' 카테고리의 다른 글

백준 1018 - 체스판 다시 칠하기  (0) 2019.08.08
백준 7568 - 덩치  (0) 2019.08.08
백준 2231 - 분해합  (0) 2019.08.07
백준 2798 - 블랙잭  (0) 2019.08.07
백준 1002 - 터렛  (0) 2019.08.06
Posted by 아야카
2019. 8. 7. 18:01
728x90

문제 번호: 2231

문제 제목: 분해합

문제 주소: https://www.acmicpc.net/problem/2231


문제 내용

분해합은 숫자 i에 i의 각 자리 수를 모두 합한 값을 의미한다. i를 분해합하여 N이 나오는 경우 i는 N의 생성자라 한다.
입력된 수 N의 생성자를 출력한다.


테스트 케이스

1

0

2

1

216

198

999999

999954

1000000

0


문제 풀이

브루트 포스로 푸는 문제지만, 1부터 시작하는건 매우 비효율적이므로 범위를 어느 정도 좁힐 필요가 있다.
생성자 수 + 생성자의 각 숫자를 모두 합해서 N이 나와야 하므로 (N - 자리수 * 9) ~ (N - 1) 이 탐색 범위가 된다.
10 이하인 수는 짝수에게만 생성자가 있으므로 그에 맞춰 코드를 작성하면 된다.


풀이 코드



728x90

'공부 > 문제풀기' 카테고리의 다른 글

백준 7568 - 덩치  (0) 2019.08.08
프로젝트 오일러 문제 18  (0) 2019.08.07
백준 2798 - 블랙잭  (0) 2019.08.07
백준 1002 - 터렛  (0) 2019.08.06
백준 3053 - 택시 기하학  (0) 2019.08.06
Posted by 아야카
2019. 8. 7. 17:37
728x90

문제 번호: 2798

문제 제목: 블랙잭

문제 주소: https://www.acmicpc.net/problem/2798


문제 내용

N개의 수열 내에서 세 개의 수를 조합하였을 때 M을 넘지 않는 근사값은 몇인지 출력한다.


테스트 케이스

5 21
6 7 8 9 10

21

5 21
10 9 8 7 6

21

3 300000
100000 100000 100000

300000

10 10
1 2 1 2 1 2 1 2 1 2

6


문제 풀이

브루트 포스로 푸는 문제다. 모든 조합을 확인하여 M과 근사한 값을 찾아내면 된다.
M과 동일한 값인 경우에는 문제의 답이 나온 것이므로 그대로 결과를 출력하고 종료하면 된다.


풀이 코드



728x90

'공부 > 문제풀기' 카테고리의 다른 글

프로젝트 오일러 문제 18  (0) 2019.08.07
백준 2231 - 분해합  (0) 2019.08.07
백준 1002 - 터렛  (0) 2019.08.06
백준 3053 - 택시 기하학  (0) 2019.08.06
백준 4153 - 직각삼각형  (0) 2019.08.06
Posted by 아야카
2019. 8. 6. 13:03
728x90

문제 번호: 1002

문제 제목: 터렛

문제 주소: https://www.acmicpc.net/problem/1002


문제 내용

2차원 좌표 A(x1, y1), B(x2, y2)가 주어지고 각 좌표에 대한 거리 r1, r2가 주어졌을 때 조건이 성립하는 점의 개수를 출력한다. 무한대일 경우에는 -1을 출력한다.
입력은 x1, y1, r1, x2, y2, r2 순서로 이루어진다.


테스트 케이스

8
0 0 13 40 0 37
0 0 3 0 7 4
0 0 2 5 5 2
0 0 12 10 0 3
0 0 12 10 0 2
0 0 12 10 0 1
1 1 1 1 1 1
1 1 1 1 1 5


2
1
0
2
1
0
-1
0


문제 풀이

케이스가 세 가지로 나뉜다. A와 B 사이에 있는 경우, A와 B사이에 있지 않은 경우, A와 B가 같은 경우.
목표가 A와 B 사이에 있는 경우에는 r1 + r2의 절대값을 A - B의 거리와 비교하여 결과를 출력하고
목표가 A와 B 사이에 없는 경우에는 r1 - r2의 절대값을 A - B의 거리와 비교하여 결과를 출력한다.
만약 A와 B의 위치가 같다면 r1와 r2를 비교하는 것만으로 충분하다.


풀이 코드



728x90

'공부 > 문제풀기' 카테고리의 다른 글

백준 2231 - 분해합  (0) 2019.08.07
백준 2798 - 블랙잭  (0) 2019.08.07
백준 3053 - 택시 기하학  (0) 2019.08.06
백준 4153 - 직각삼각형  (0) 2019.08.06
백준 3009 - 네 번째 점  (0) 2019.08.06
Posted by 아야카
2019. 8. 6. 11:52
728x90

문제 번호: 3053

문제 제목: 택시 기하학

문제 주소: https://www.acmicpc.net/problem/3053


문제 내용

반지름 R이 주어졌을 때 유클리드 기하학에서의 원의 넓이와 택시 기하학에서의 원의 넓이를 출력한다.


테스트 케이스

1

3.141593
2.000000

2

12.566371
8.000000


문제 풀이

설명에 원이라는 표현이 들어가서 혼란이 있을 수 있지만 택시 기하학에서 같은 거리라는 것은 각 변의 길이가 동일한 마름모 모양을 의미한다. #참고링크 
따라서 택시 기하학의 넓이는 R * R * 2로 나타낼 수 있다.
유클리드 기하학과 관련하여 소수점 6자리까지 출력되어야 하므로 cout << fixed를 해줘야 한다.
이 문제에서 사용하는 π는 소수점 12자리까지 필요하며 (3.141592653589), cmath 상수인 M_PI를 이용해도 무방하다.


풀이 코드

728x90

'공부 > 문제풀기' 카테고리의 다른 글

백준 2798 - 블랙잭  (0) 2019.08.07
백준 1002 - 터렛  (0) 2019.08.06
백준 4153 - 직각삼각형  (0) 2019.08.06
백준 3009 - 네 번째 점  (0) 2019.08.06
백준 1085 - 직사각형에서 탈출  (0) 2019.08.06
Posted by 아야카
2019. 8. 6. 11:16
728x90

문제 번호: 4153

문제 제목: 직각삼각형

문제 주소: https://www.acmicpc.net/problem/4153


문제 내용

주어진 세 변의 길이로 직각삼각형 유무를 출력한다. 맞을 경우에는 right, 틀릴 경우에는 wrong을 출력한다.
0 0 0 이 입력되면 종료한다.


테스트 케이스

6 8 10
25 52 60
5 12 13
0 0 0

right
wrong
right


문제 풀이

입력된 값 A, B, C에 대해 각 변에 대한 제곱합을 비교하면 된다.
A * A + B * B == C * C
B * B + C * C == A * A
C * C + A * A == B * B


풀이 코드



728x90

'공부 > 문제풀기' 카테고리의 다른 글

백준 1002 - 터렛  (0) 2019.08.06
백준 3053 - 택시 기하학  (0) 2019.08.06
백준 3009 - 네 번째 점  (0) 2019.08.06
백준 1085 - 직사각형에서 탈출  (0) 2019.08.06
백준 9020 - 골드바흐의 추측  (0) 2019.08.06
Posted by 아야카
2019. 8. 6. 11:08
728x90

문제 번호: 3009

문제 제목: 네 번째 점

문제 주소: https://www.acmicpc.net/problem/3009


문제 내용

점 세 개가 주어졌을 때 직사각형을 이룰 수 있는 네 번째 점을 출력한다.


테스트 케이스

30 20
10 10
10 20

30 10

10 10
30 10
10 20

30 20

10 20
30 10
30 20

10 10

30 20
10 10
30 10

10 20


문제 풀이

사각형 중 모자란 한 점을 찾는 것이므로 세 점에서 짝이 없는 수를 찾으면 된다.
XOR 연산자는 비트가 서로 다르면 1, 같으면 0이 된다. 이와 관련하여 갖는 성질로 아래 두 가지가 있다.
1. 값이 0인 변수에 A 값의 XOR 연산을 하면 해당 변수는 A가 된다.
 - 모든 비트가 0이므로 1인 비트에 대한 부분만 1이 되기 때문
2. 값이 A인 변수에 B 값의 XOR 연산을 두 번 하면 원래의 값 A가 된다.
 - 최초 연산일 때 값이 변경된 부분만 다시 변경되기 때문.
 - 예시) 01010101 ^ 00110011 ^ 00110011 = 01100110 ^ 00110011 = 01010101
이러한 성질을 이용하면 사각형의 나머지 꼭지점을 빠르게 찾아낼 수 있다.


풀이 코드

728x90

'공부 > 문제풀기' 카테고리의 다른 글

백준 3053 - 택시 기하학  (0) 2019.08.06
백준 4153 - 직각삼각형  (0) 2019.08.06
백준 1085 - 직사각형에서 탈출  (0) 2019.08.06
백준 9020 - 골드바흐의 추측  (0) 2019.08.06
백준 4948 - 베르트랑 공준  (0) 2019.08.06
Posted by 아야카
2019. 8. 6. 10:50
728x90

문제 번호: 1085

문제 제목: 직사각형에서 탈출

문제 주소: https://www.acmicpc.net/problem/1085


문제 내용

(0, 0)과 (w, h)를 꼭지점으로 하는 직사각형 내의 (x, y)에서 직사각형을 벗어나는 최소 거리를 출력한다.
입력은 x y w h 순서로 이루어진다.


테스트 케이스

1000 1000 999 1

1

1000 1000 999 999

1

1000 1000 1 1

1

1000 1000 1 999

1

1000 1000 500 500

500


문제 풀이

x, y, w-x, h-y를 각각 비교하여 가장 작은 수를 출력하면 된다.


풀이 코드



728x90

'공부 > 문제풀기' 카테고리의 다른 글

백준 4153 - 직각삼각형  (0) 2019.08.06
백준 3009 - 네 번째 점  (0) 2019.08.06
백준 9020 - 골드바흐의 추측  (0) 2019.08.06
백준 4948 - 베르트랑 공준  (0) 2019.08.06
백준 1929 - 소수 구하기  (0) 2019.08.06
Posted by 아야카