acmicpc.net 1931(그리디), 1744(그리디?), 2846

그리디(greedy) : 현재 상태에서 가장 최적의 답을 구함. 현재 상태에서의 최적의 답이 '최고'의 답이 아닐지라도 그냥 최적의 상태를 고름. 경우의 수가 너무 많은 경우 그냥 이 알고리즘을 씀.

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

그리디 문제.

# -*- encoding: cp949 -*-
n = int(raw_input())
conf = sorted([map(int,raw_input().split()) for i in xrange(n)],key=lambda x:(x[1],x[0])) #입력받은후 끝나는 시간,시작되는 시간 기준으로 정렬
con_list = [conf[0]]
for i in xrange(1,len(conf)): #돌아가면서 현재 맨 끝의 회의의 끝나는 시간보다 현재 있는 회의의 시간이 크면 그냥 넣어줌.
    if conf[i][0] >= con_list[-1][1]:
        con_list.append(conf[i])
print len(con_list)

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

그리디 문제라는데... 그냥 풀면 됬다.

# -*- encoding: cp949 -*-
n = int(raw_input())
plus = []; minus = []
for i in xrange(n): #입력받아서
    num = int(raw_input())
    plus.append(num) if num > 0 else minus.append(num)

p_m = [sorted(plus,reverse=True),sorted(minus)] #플러스와 마이너스 범위를 따로 정렬해서 저장함.
answer = 0
for k in xrange(2): #플러스따로 마이너스따로
    p_m_count = 1 if len(p_m[k])%2==0 else 2 #각각 리스트가 짝수개면 1을빼고, 홀수개면 2를뺀만큼 반복문돌림
    for i in xrange(0,len(p_m[k])-p_m_count,2):
        answer += p_m[k][i]*p_m[k][i+1] #곱한것이 무조건 크므로 곱한값을 더해줌.
        if p_m[k][i] == 1 or p_m[k][i+1] == 1: #그런데 1 1일경우에는 곱하는것보다 1+1이 더큼. 그러므로 1이 있을 경우에는 1씩 더해줌
            answer += 1
    answer += p_m[k][-1] if p_m_count==2 else 0 #홀수일경우 끝에 한개가 남으므로 끝원소 더해줌

print answer

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

문제를 읽어보면 왠지 dp같다. 근데 N(1 ≤ N ≤ 1000) Pi(1 ≤ Pi ≤ 1000) 이다. 최악의 경우에도 

백만개밖에 반복문이 안돈다는 소리이다. 그래서 그냥 돌렸는데 답이 나왔다....

# -*- encoding: cp949 -*-
def to_up():
    ret = 0
    for i in xrange(len(p)-1):
        b = []
        flag = False
        for j in xrange(i,len(p)):
            if j==len(p)-1 and flag:
                b.append(p[j])
                break
            if j<len(p)-1 and p[j] < p[j+1]:
                b.append(p[j])
                flag = True
            elif flag: 
                b.append(p[j])
                break
        if b!=[]:
            ret = b[-1]-b[0] if b[-1]-b[0] > ret else ret
    return ret
 
n = int(raw_input())
p = map(int,raw_input().split())
print to_up()