2019. 8. 1. 13:06
728x90

문제 번호: 2869

문제 제목: 달팽이는 올라가고 싶다

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


문제 내용

낮에는 A미터 올라가고, 밤에는 B미터 미끄러지는 달팽이가 V미터 높이를 오르는데 소요되는 일수를 출력한다.


테스트 케이스

2 1 5

4

4 2 5

2

2 1 1000000000

999999999


문제 풀이

반복문을 사용하여도 결과는 올바르게 나오지만 이 경우 C++로 진행하여도 제한시간인 0.15초를 초과하게 된다. 따라서 반복문이 아닌 단순 수식으로 처리하여 결과를 출력해야 한다.
마지막 날에는 올라가기만 하고 미끄러지지 않고, 그 외의 날짜는 하루치 이동거리만큼 이동하고, 반복문으로 돌리는 것도 동일한 값의 뺄셈이 반복되는 것이니 / 연산자를 활용하는게 낫다. 과정은 아래와 같다.

1. 날짜 값을 1로 초기화 한다.
2. V에서 A를 뺀다.
3. V를 (A - B)로 나눈 나머지가 0인지 확인한다.
 3.1. true라면 V / (A - B) + 1을 출력한다.
 3.2. false라면 V / (A - B) + 2를 출력한다.


풀이 코드



728x90

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

백준 2775 - 부녀회장이 될테야  (0) 2019.08.02
백준 10250 - ACM 호텔  (0) 2019.08.02
백준 1011 - Fly me to the Alpha Centauri  (0) 2019.08.01
백준 1193 - 분수찾기  (0) 2019.07.31
백준 2292 - 벌집  (0) 2019.07.31
Posted by 아야카
2019. 8. 1. 12:35
728x90

문제 번호: 1011

문제 제목: Fly me to the Alpha Centauri

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


문제 내용

아래의 규칙을 통해 x에서 y로 이동하는데 필요한 최소한의 이동 횟수를 출력한다.
1. 최초 기준값 k는 0이다.
2. 이동 시에는 k - 1, k, k + 1 중 하나의 거리만큼 이동할 수 있다.
3. 다음 이동 시의 기준값을 직전에 이동한 거리가 된다.
4. 도착 시의 이동 거리는 1 이어야 한다.
5. 정지 또는 후진이 불가능하다.


테스트 케이

6
0 1
1 3
3 6
6 10
10 15
0 2147483647


1
2
3
3
4
92681


문제 풀이

이동 속도의 변화량은 1로 제한되어 있는데 도착 직전의 이동 거리가 1이어야 한다.
따라서 속도를 가속하다 중간 지점부터 감속을 해야 한다.
이를 그래프로 나타내면 아래와 같다.

위와 같이 이동 횟수별 이동 거리는 좌우대칭 형태를 이루고 있다.
현재의 (1회당 이동거리) * 2를 거리에서 빼는 작업을 거리가 0보다 작거나 같아질 때까지 반복하고
1. 거리 = 거리 - (1회당 이동 거리) * 2
2. 이동 횟수 +2
3. 거리가 0보다 작거나 같은가?
4. 아닐 경우 1회당 이동거리 +1
위 과정의 반복 완료 후에 (거리 + 1회당 이동거리) <= 0이 true일 경우 이동 횟수 -1을 하면 된다.


풀이 코드


728x90

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

백준 10250 - ACM 호텔  (0) 2019.08.02
백준 2869 - 달팽이는 올라가고 싶다  (0) 2019.08.01
백준 1193 - 분수찾기  (0) 2019.07.31
백준 2292 - 벌집  (0) 2019.07.31
백준 2839 - 설탕 배달  (0) 2019.07.28
Posted by 아야카
2019. 7. 31. 23:18
728x90

문제 번호: 1193

문제 제목: 분수 찾기

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


문제 내용

1/1

1/2

1/3

1/4

1/5

2/1

2/2

2/3

2/4

...

3/1

3/2

3/3

...

...

4/1

4/2

...

...

...

5/1

...

...

...

...

 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> ... 과 같은 순서로 진행되는 배열에서 X 번째 분수를 출력한다.


테스트 케이스

1

1/1

4

3/1

6

1/3

7

1/4

1000000000

6282/38440


문제 풀이

1번째 대각선은 1/1
2번째 대각선은 1/2 -> 2/1
3번째 대각선은 3/1 -> ... -> 1/3
4번째 대각선은 1/4 -> ... -> 4/1
5번째 대각선은 5/1 -> ... -> 1/5

짝수 번째 대각선은 1/n -> n/1로 진행되고 (분자 증가, 분모 감소)
홀수 번째 대각선은 n/1 -> 1/n으로 진행된다. (분자 감소, 분모 증가)
따라서 X번째 수는 1 ~ (n - 1)까지의 합계를 X에서 제거한 뒤
n이 짝수인 경우에는 X / (n - X + 1)
n이 홀수인 경우에는 (n - X + 1) / X가 된다.
위 규칙을 적용하여 코드를 작성하면 된다.


풀이 코드


728x90

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

백준 2869 - 달팽이는 올라가고 싶다  (0) 2019.08.01
백준 1011 - Fly me to the Alpha Centauri  (0) 2019.08.01
백준 2292 - 벌집  (0) 2019.07.31
백준 2839 - 설탕 배달  (0) 2019.07.28
백준 1712 - 손익분기점  (0) 2019.07.28
Posted by 아야카
2019. 7. 31. 22:43
728x90

문제 번호: 2292

문제 제목: 벌집

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


문제 내용

위와 같은 구조에서 숫자 N이 입력됐을 때 1에서 N까지 이동하는데 최소 몇 칸을 지나지는지 출력한다.


테스트 케이스

1

1

2

2

7

2

8

3

1000000000

18258


문제 풀이

1칸 이동에 해당하는 1은 총 총 1칸
2칸 이동에 해당하는 2~7은 총 6칸
3칸 이동에 해당하는 8~19는 총 12칸
4칸 이동에 해당하는 20~37은 총 18칸
5칸 이동에 해당하는 38~61은 총 24칸
2부터 이동 칸에 따라 총 칸 수가 6의 배수만큼 증가하는 것을 알 수 있다.
따라서 N이 1일 때를 제외한 나머지에 대해서는 N을 i*6만큼 제거하는 것으로 몇 칸이 소요되는지 알 수 있다.


풀이 코드


728x90

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

백준 1011 - Fly me to the Alpha Centauri  (0) 2019.08.01
백준 1193 - 분수찾기  (0) 2019.07.31
백준 2839 - 설탕 배달  (0) 2019.07.28
백준 1712 - 손익분기점  (0) 2019.07.28
백준 1316 - 그룹 단어 체커  (0) 2019.07.28
Posted by 아야카
2019. 7. 28. 15:22
728x90

문제 번호: 2839

문제 제목: 설탕 배달

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


문제 내용

지정된 무게 N을 달성하기 위해 3과 5가 합해서 최소 몇 개가 필요한지 출력한다. 없을 경우 -1을 출력한다.


테스트 케이스

18

4

4

-1

6

2

9

3

11

3


문제 풀이

0. 수를 입력 받을 N, 결과를 저장할 result 변수를 생성한다.
 > result는 -1로 초기화 한다.
1. 입력된 수 N을 5로 나눈 몫 A를 구한다.
2. for문을 A부터 시작하여 0까지 진행한다.
 2.1. N을 5로 나눈 나머지를 3으로 나눌 수 있는지 확인한다.
 2.1.1. 나눌 수 있는 경우 i와 나머지를 3으로 나눈 몫을 합하여 결과에 저장한다.
 2.1.2. break;
3. 결과 출력.


풀이 코드

728x90

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

백준 1193 - 분수찾기  (0) 2019.07.31
백준 2292 - 벌집  (0) 2019.07.31
백준 1712 - 손익분기점  (0) 2019.07.28
백준 1316 - 그룹 단어 체커  (0) 2019.07.28
백준 2941 - 크로아티아 알파벳  (0) 2019.07.26
Posted by 아야카
2019. 7. 28. 15:11
728x90

문제 번호: 1712

문제 제목: 손익분기점

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


문제 내용

고정 비용, 생산가, 판매가가 주어졌을 때 손익분기점이 되는 판매 수량을 출력한다.


테스트 케이스

1000 70 170

11


문제 풀이

생산가가 판매가와 같거나 높은 경우에는 -1을.
그 외에는 고정 비용 / (판매가 - 생산가) + 1을 출력한다.


풀이 코드



728x90

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

백준 2292 - 벌집  (0) 2019.07.31
백준 2839 - 설탕 배달  (0) 2019.07.28
백준 1316 - 그룹 단어 체커  (0) 2019.07.28
백준 2941 - 크로아티아 알파벳  (0) 2019.07.26
백준 5622 - 다이얼  (0) 2019.07.26
Posted by 아야카
2019. 7. 28. 14:58
728x90

문제 번호: 1316

문제 제목: 그룹 단어 체커

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


문제 내용

입력 받은 N개의 문자열 중에서 그룹 단어 수를 출력한다.
그룹단어: 단어 내에서 같은 글자가 연속해서만 나타나는 경우. 같은 글자가 서로 떨어져서 있는 경우에는 그룹단어가 아니다.
 - happy (O), assist (X)


테스트 케이스

3
happy
new
year

3

4
a
aba
aabb
abcabc

2


문제 풀이

알파벳 인덱스에 상태를 입력하고 이를 바탕으로 그룹 단어인지 체크한다.
0 - 확인하지 않은 알파벳
1 - 확인된 알파벳
혹은 배열에 알파벳을 넣고 배열 내에 해당하는 알파벳이 있는지 체크하는 방식으로 하여도 된다.


풀이 코드


728x90

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

백준 2839 - 설탕 배달  (0) 2019.07.28
백준 1712 - 손익분기점  (0) 2019.07.28
백준 2941 - 크로아티아 알파벳  (0) 2019.07.26
백준 5622 - 다이얼  (0) 2019.07.26
백준 2908 - 상수  (0) 2019.07.26
Posted by 아야카
2019. 7. 26. 03:51
728x90

문제 번호: 2941

문제 제목: 크로아티아 알파벳

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


문제 내용

입력받은 문장을 크로아티아 알파벳 기준으로 총 몇 글자인지 출력한다.


테스트 케이스

ljes=njak

6

ddz=z=

3

nljj

3

c=c=

2

d-ljoinjdz

7


문제 풀이

dz=에 대한 처리만 주의해서 하면 문제될 건 없다.
현재 텍스트가 c, d, l, n, s, z인가에 대해 확인하고, 해당할 경우 다음 글자가 무엇인가를 확인하여 
크로아티아 알파벳에 부합하면 해당 글자만큼 건너뛰는 식으로 글자수를 집계하면 된다.


풀이 코드



728x90

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

백준 1712 - 손익분기점  (0) 2019.07.28
백준 1316 - 그룹 단어 체커  (0) 2019.07.28
백준 5622 - 다이얼  (0) 2019.07.26
백준 2908 - 상수  (0) 2019.07.26
백준 1152 - 단어의 개수  (0) 2019.07.26
Posted by 아야카