[Java] 구두 수선공 문제 (shoemaker's problem) - UVa 10026 문제

[Java] 구두 수선공 문제 (shoemaker's problem) - UVa 10026 문제

 

 

 

onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=967

 

Online Judge

 

 

문제 설명

 

내 코드

 

 

 

👑 Key Point

인접한 두개의 곱셈을 이용하여 Index 행렬을 정렬하는 것이라 버블정렬을 이용하는것이 매우 쉽게 풀 수 있다.

if(T[priority[y]]*P[priority[y+1]]>T[priority[y+1]]*P[priority[y]])

다만 Bubble 정렬의 조건식 부분에서 T,P 에들어가는것은 버블정렬에 사용되는 index가 index행렬의 값 이 들어가야한다 . (매우 중요한 개념 ! ) 

처음에는 아무 생각없이 

 

if(T[y]*P[y+1]>T[y+1]*P[y])

라고 썻다. 당연히 틀릴 수 밖에.. 차이점이 보여야 한다!

 

조건식에서 바꿔줄 것은 T,P행렬이 아닌 조건문에서 사용되지 않은 Index 행렬이다.

따라서 y를 바로 쓰게 되면 안되고 바뀐 Index의 값을 계속 업데이트하여 조건문에서 비교해주어야 한다. 

그래서 y 가아닌 index의 값인  priority[y]가 인덱스 로 들어가야한다.