수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/1543

-정답풀이:

아이디어는 맞았는데, 세세한 부분이 부족해서 헤맸다 

종료 조건과, else문 설정을 정확히 하지 않아서 시간초과가 났다

그래도 인덱스 슬라이싱으로 문자 비교하려고한 건 맞았다

first=list(input())
second=list(input())
n=len(second)
m=len(first)
count=0
start=0
end=n

while True:
    if start > m-n :
        break
    if first[start:end] == second:
        count+=1
        start=start+n
        end=end+n
    else: 
        start+=1
        end+=1
                            
print(count)

-이전 풀이

first=list(input())
second=list(input())
n=len(second)
m=len(first)
count=0
start=0
end=n-1

while True:
    if start > m-n-1 :
        break
    if first[start:end] == second:
        count+=1
        start=end+1
        end=end+n-1
                            
print(count)

-문제 : https://www.acmicpc.net/problem/2437

Gold Level2 문제

2022.11.01에 풀이 추가

풀이 이해

간단하지만 도무지 이해가 가지 않아서 구글링을 했다.

풀이 아이디어는 weights[i]가 추가될 때마다 측정 가능한 무게의 범위가 증가하는데, 이게 연속적일 수도 아닐 수도 있다. 

그래서 새로 추가된 부분이 연속적이지 않을 때, 그때의 시작 부분을 반환하면 된다

참고한 블로그

-정답풀이: 

이 문제도 그리디에서 변수에 값 저장한 후 단일 반복문으로 푸는 문제다 

이 유형 문제는 언제쯤 답 없이 풀 수 있을까ㅠㅠㅠㅠ 풀고 싶다 

n=int(input())
data=list(map(int,input().split()))
data.sort()
result=0

for i in range(n):
    if result + 1 >= data[i]:
        result += data[i]
    else:
        break
        
print(result+1)

-메모리 초과한 풀이

combination으로 모든 경우의 수를 구하고, 그것의 합을 구한 다음, 그 중에 없는 가장 작은 값을 출력하는 방법을 생각했다.

역시나 메모리 초과가 떴다 

import itertools

n=int(input())
data=list(map(int,input().split()))
result=[]
for i in range(n):
    result.append(data[i])

for i in range(2,n):
    temp = list(itertools.combinations(data,i))
    for j in range(len(temp)):
        result.append(sum(temp[j]))
    
    
result.sort()
i=1
while True:
    if i not in result:
        answer=i
        break
    i+=1
print(answer)

-문제 :https://www.acmicpc.net/problem/1449

-정답풀이 :

l단위 만큼 이동하면서 그 범위안에 leak이 포함된다면 통과하고, 아니면 테이프를 붙이고 갯수를 늘려가는 방식으로 진행한다

n,l = map(int,input().split())
leak = list(map(int,input().split()))
leak.sort()
count=1
start=leak[0]
end=leak[0]+l
for i in range(n):
    if start <= leak[i] < end:
        continue
    else:
        start=leak[i]
        end=leak[i]+l
        count+=1
print(count)

-IndexError가 난 풀이

pythontutor로 예시 돌렸을 땐 다 정답이 나오는데 왜 계속 IndexError가 나는지 모르겠다

n,l = map(int,input().split())
leak = list(map(int,input().split()))
leak.sort()
result=[0]*(1001)
count=0

for i in range(n):
    if result[leak[i]]==0:
        for j in range(leak[i],leak[i]+l+1):
            result[j]=1
        count+=1
    else:
        continue
print(count)

-문제 : https://www.acmicpc.net/problem/1080 

처음에 풀었을 때 되게 어렵게 느껴졌던 문제였는데, 다시 풀어보니까 그렇게 어렵지는 않았다 

문제에서 연산은 3x3 행렬 단위로 이루어진다고해서 3x3 행렬 단위로 진행해야된다고 생각했다. 

그런데 차근차근 3x3단위로 이동해야한다고 생각해 이중 반복문을 생각했는데 이게 아니라

완전 탐색하면서 다른 지점이 있을 때마다 3x3 단위로 변환을 하면 된다. 

변환하는 것은 1-원래값으로 한다 

다른 블로그에는 위 방식이었지만, 나는 이해가 가지 않아 그냥 조건에 따라서 값을 변경하는 것으로 바꿨다

변환할 때마다 연산횟수를 더해가면 된다

완전 탐색시 범위가 중요한데 3x3단위로 진행하므로 마지막 인덱스틑 n-3이 되어야 n-3,n-2,n-1을 변환해서 

인덱스 오류가 나지 않는다 

-1을 출력하는 것은 변환을 마쳤는데도 다른 지점이 있으면 True값 저장해서 -1 출력하면 되고

else에 대해서는 count를 출력하면 된다 

-정답 풀이 

n,m=map(int,input().split())
A,B = [], []
count=0
for _ in range(n):
    A.append(list(map(int,input())))
for _ in range(n):
    B.append(list(map(int,input())))             

def convert3x3(x,y,A):
    for i in range(x,x+3):
        for j in range(y,y+3):
            if A[i][j]==1:
                A[i][j]=0
            else:
                A[i][j]=1

#convert3x3이 3단위라서 n-3이 제일 마지막이 되어야한다(n-3,n-2,n-1)
#안 그럼 인덱스 오류남              
for a in range(n-2):
    for b in range(m-2):
        if A[a][b] != B[a][b]:
            convert3x3(a,b,A)             
            count+=1
            
isTrue = False
for i in range(n):
    for j in range(m):
        if A[i][j] != B[i][j]:
            isTrue=True
                                                
if isTrue:
    print(-1)
else:
    print(count)