https://www.acmicpc.net/problem/1065


1. 문제 이해


각 자리 수가 등차 수열이 된다면 그 수는 한수 입니다.




2. 접근방법


for문을 이용한 완전탐색을 이용하여 한수를 찾아 보겠습니다.


저는 이 문제의 포인트를 자릿수로 정했습니다.

문제의 조건이 1000이하의 자연수 이므로 1자리에서 3자리 까지만을 고려하면 됩니다.


크게 두가지의 경우로 나뉘게 되는데,


첫 번째, 한 자리수와 두 자리수는 그 자체가 등차 수열이 되므로 곧바로 한수 카운트를 올려줍니다.


두번째, 세자리의 수의 경우에는 

'백의자리수 - 십의자리수 = 십의자리수 - 일의자리수' 조건이 같게 되다면 한수 카운트를 올려줍니다.



3. 문제 해결


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
using namespace std;
 
int n, res;
 
void hansu_cnt(int cur) {
    if (cur / 100 - (cur / 10) % 10 == (cur / 10) % 10 - cur % 10) {
        res++;
    }
}
 
int main() {
    cin >> n;
 
    if (n > 99) {
        res = 99;
        for (int i = 100; i <= n; i++) {
            hansu_cnt(i);
        }
    }
    else {
        res = n;
    }
    cout << res << '\n';
}
cs


'Algorithm > solution' 카테고리의 다른 글

#1463. 1로 만들기  (0) 2017.12.24
#10815. 숫자카드  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23
#11866. 조세퍼스 문제  (0) 2017.12.01
#10828. 스택  (0) 2017.11.29

https://www.acmicpc.net/problem/1654

1. 문제 이해

 저 같은 경우는 문제 이해에서 완벽하게 넘어가지 않아 꽤나 고생했던 문제입니다.

함정 point는 n개의 똑같은 랜선을 만들어야 하는데 n보다 큰 경우인 n+1, n+2 경우에도 최대값을 체크해 줘야 한다는 것 입니다.


2. 접근방법

두가지 부분에서 조심해야 합니다.


첫 번째, 시간초과에 주의해야 합니다. 

완전탐색을 할 경우,  시간이 초과하기 때문에 binary search를 사용해야 합니다.


두 번째, 범위초과에 주의해야 합니다.

int 형으로 선언할 경우, 범위가 초과하는 경우(예를 들어, left(2^31-1 / 2)+right(2^31) / 2 = mid(int형 초과), 잘린 갯수(1로 잘랐을대 int형 초과))가 발생할 수 있기 때문에 long long형을 사용하도록 합니다.


세 번째,

저 같은 경우는 속도를 올리기 위해서 

'가장 작은 값을 기준으로 0부터 가장 작은 값 까지 이분탐색을 하자!' 로 접근하였습니다.

하지만 이렇게 접근한 경우, 밑의 test case 에서는 0이 출력 되버립니다. 즉, 완전 탐색이 할 필요가 있다는 것입니다.

4 5

100

200

302

400

그래서 최대값을 찾아 접근하여야 합니다. 최대값으로 설정할경우에도 이분탐색으로 탐색하기 때문에 O(logN) 이 되므로 시간 초과에 대해서 걱정 하지 않아도 됩니다.

3. 문제 해결

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#define MAX_SIZE 10005
 
using namespace std;
 
int k, n;
long long res;
int arr[MAX_SIZE];
 
long long calc_lens(long long len) {
    long long output = 0;
    for (int i = 0; i < k; i++) {
        output += (arr[i] / len);
    }
    return output;
}
 
int main() {
    scanf("%d %d"&k, &n);
 
    long long _max = 0;
    for (int i = 0; i < k; i++) {
        scanf("%d"&arr[i]);
        _max = _max < arr[i] ? arr[i] : _max;
    }
 
    long long l = 1, r = _max;
    while (l <= r) {
        long long mid = (l + r) / 2;
        long long tmp = calc_lens(mid);
 
        if (tmp < n) {            // 크게 잘른것, 자르는 크기 줄여주기
            r = mid - 1;
        }
        else {                    // 크거나 같은경우
            res = res < mid ? mid : res;
            l = mid + 1;
        }
    }
 
    printf("%lld\n", res);
    return 0;
}
cs



※ long long 형은 9byte로 int(4byte)보다 더 많은 수를 표현할 수 있다.

※ MAX_SIZE 실수를 자꾸 한다.... 시간 초과가 날 경우 용량을 잘 확인하자!!!

'Algorithm > solution' 카테고리의 다른 글

#10815. 숫자카드  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#11866. 조세퍼스 문제  (0) 2017.12.01
#10828. 스택  (0) 2017.11.29
#1874. 스택수열  (1) 2017.11.29

● PROCESS : 실행중인 프로그램

       ------------------> 자원 + 공간(*) + 쓰레드(**) 로 이뤄짐.


  * 자원        : 공간(호출스택)의 크기에 따라 호출할 수 있는 쓰레드의 수가 결정된다.

  ** 쓰레드    : 쓰레드의 갯수에 따라 싱글 쓰레드와 멀티 쓰레드로(***) 나뉜다. 


  *** < 멀티 쓰레드의 장점 >

                                  

1. cpu의 활용률 향상                                     

2. 자원을 보다 효율적으로 사용                         

3. 사용자에 대한 응답성 향상                           

4. 작업이 분리 되기 때문에 코드가 간결해진다.

=> 쓰레드와 사용자 요청이 1:1 대응이 되도록 프로그래밍 해야 한다.


< 멀티 쓰레드의 단점 > --> 이 부분에 대해선 뒤에서 자세히 다루자.


1. 동기화 문제

2. 교착상태

=> 여러 쓰레드가 자원을 공유하면서 작업을 하기 때문에 발생.


cf> 프로세스의 성능이 쓰레드의 개수와 비례하진 않는다.



● 쓰레드 구현 방법

 

1. Thread 클래스 상속

   -> But, Thread클래스를 상속받으면 다른 클래스를 상속 받을 수 없다.


2. Runnable 인터페이스 구현.

   -> 이 방법을 주로 

 ex>

1
2
3
class MyThread implements Runable {
    public void run() { /* 작업 내용 */ }
}
cs


● 한번 사용한 쓰레드는 재 사용될 수 없다. (즉, 한번 start() 한 것을 또 start()할 수 없다.)

 


● 예시를 통해 호출스택 내부를 살펴보도록 하자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ThreadEx3 {
 
    public static void main(String[] args) throws Exception {
        MyThreadEx3_1 t1 = new MyThreadEx3_1();
        t1.run();
    }
 
}
 
class MyThreadEx3_1 extends Thread {
    public void run() {
        throwException();
    }
    
    public void throwException() {
        try {
            throw new Exception();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
cs


실행결과

java.lang.Exception

at GodBell.MyThreadEx3_1.throwException(ThreadEx3.java:19)

at GodBell.MyThreadEx3_1.run(ThreadEx3.java:14)                        

at GodBell.ThreadEx3.main(ThreadEx3.java:7)

 

 

: 이 예제는 고의적으로 예외를 발생시켜서 호출스택의 내용을 확인할 수 있도록 했다.

 (start() 메서드가 아니라 run()메서드 이기 때문에 main()메서드가 호출스택에 포함되어 있음을 확인할 수 있다.)

 

● start VS run

 

start() : 쓰레드 실행 (새로운 호출 스택 생성)

run()  : 단순히 클래스에 속한 메서드 하나를 호출

 

cf> start()가 호출된 쓰레드는 바로 실행되는것이 아니고, 일단 대기상태에 있다가 스케줄러가 정한 순서에 의해 실행.

     실행중인 쓰레드가 하나도 없을 때 program은 종료된다. 

 

 

 

 

● 싱글 쓰레드 VS 멀티 쓰레드

 

 - cpu 만을 사용하는 계산 작업이라면 오히려 싱글 쓰레드가 더 빠르다.

   why)) 스위칭 때문!! (다음에 실행하는 위치(PC)등의 정보를 저장하고 읽어오는 시간이 소요된다.)

 

 - 프린트기 사용이나 다른 입력장치와 함께 사용할때에는 멀티쓰레드가 더 좋다. 

 

 

● 쓰레드는 우선순위 속성을 가지고 있다.

 

 - 우선순위 (1 ~ 10) : 클수록 우선순위가 높다.

 - 절대적이 아니라 상대적인 개념.

ex> 1, 2    ==    9, 10    

     (두 경우 모두 우선순위가 1차이 만큼 우선순위 속성을 가지고 있다.)

 - main의 쓰레드의 우선순위는 '5'이므로 main 내의 생성한 쓰레드는 우선순위 '5'를 갖게된다.

 

 

● 쓰레드 그룹

 

 - 그룹 : 폴더개념이라고 생각하자.

 - 보안상의 이유로 만들어졌다. (자신이 속한 그룹이거나, 하위그룹 쓰레드는 변경 가능 하지만 다른 그룹의 쓰레드는 내용 변경 불가!)

 - 모든 쓰레드는 그룹에 포함되어야 한다.

 

 - ThreadGroup(String name)을 사용해서 그룹 생성 가능.

 - 쓰레드 그룹에 포함시키려면 "생성자"를 이용해야 한다.

   if> 생성자를 안썻다면?

: 자신을 생성한 쓰레드와 같은 그룹에 속하게 된다.

 

=> 즉, 우리가 생성한 모든 쓰레드는 모두 main 쓰레드 그룹에 속하게 된다.

 

 

~641 PAGE 부터 이어집니다.... (데몬 쓰레드 부터 시작) 



'cs > os' 카테고리의 다른 글

#3-3. Thread  (0) 2017.12.29
#3-2. Process  (0) 2017.12.27
#3-1. Process  (0) 2017.12.27
#2-2. System Structure & Program Execution  (0) 2017.12.25
#2-1. System Structure & Program Execution  (0) 2017.12.24

+ Recent posts